Create Target Array

PROBLEM STATEMENT

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

Approach 2

For this approach, we will try to think about solving this problem backward, i.e., we will try to generate the array of 1s from the target array.

We know that while working backward the maximum element of the array will be the sum of elements after the last turn. To keep track of the maximum element, we will use a max heap.

After every turn, we will remove the maximum element from the heap and determine the previous maximum element value. To do this we will be needing the sum of all elements of the array.

Let’s say “sum” is the sum of all elements and “ lastSum” is the maximum element or the last sum of the array. To determine the previous element, we difference of “sum” and “lastSum” from “lastSum”, i.e (lastSum - (sum - lastSum)).

Then we put this value back to the heap and update the sum.

We continue this until either the sum is equal to one OR the “lastSum” is equal to one to return true.

In case, “lastSum” becomes less than sum OR sum becomes equal to zero OR the difference of “lastSum” and “sum” becomes zero, return false.

Try Problem