Create Target Array

Posted: 13 Apr, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given an array of integers. Starting with an array of 'N' elements consisting of all 1’s, you need to create the given array. To do so, you can update any index of the current array, with the sum of all elements present in the array.

For example:
Consider the starting array: [1, 1, 1, 1]. You can update any index of this array with 4 (the sum of all elements of the current array).

You can perform the above operations any number of times. Your task is to check if it is possible to get the target array from the starting array of all 1’s or not.

Input Format:
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains a single integer ‘N’, denoting the size of the target array.

The next line contains ‘N’ space-separated integers denoting elements of the target array.
Output Format:
For each test case, print 1 if it is possible to create the target array, otherwise print 0.

Print the output of each test case in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
1 <= X <= 10^9

Time limit: 1 sec
Approach 1

The basic idea is that we will start from an array ‘arr’ having all elements as 1. We will create all possible arrays by placing the sum of all elements of ‘arr’ at all the positions of ‘arr’ and doing this recursively. 

 

If at any moment all the elements of the array 'arr' become equal to our target array, then we will return 1. Otherwise, if any of the elements of the ‘arr’ array becomes greater than its corresponding element in the target array, then we can not create the target array from this ‘arr’ array. 

 

So recursion will stop here and we will return 0. The above two steps serve as the base case.

 

The answer at any step will be the Bitwise OR of all the recursive calls made from that function.

 

Algorithm:

 

  • Let createTarget(arr, target, sum) be our recursive function where “arr” is the array that we have to update, “target” is the given target array, and “sum” is the sum of elements of the “arr” array.
  • Base Case
    • If for any index ‘i’, target[i] < arr[i], return false.
    • If all the elements of the “arr” and “target” array are the same, then we will return 1.
  • Initialize a variable “ans” to store the result.
  • Iterate through the “arr” array using the variable “i”.
    • Copy the “arr” array in another array “arrCopy”.
    • Update arrCopy[ i ] as “sum”.
    • Recursively call for the “arrCopy” array.
      • ans is ans OR createTarget(arrCopy, target, sum - arr[i] + sum).
  • Return ans.
Try Problem