Create Target Array

Hard
0/120
Average time to solve is 35m
profile
Contributed by
10 upvotes
Asked in companies
AdobeSpinny

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
2 3
3
1 3 6
Sample Output 1:
1
0
Explanation For Sample Input 1:
In the first test case, 

Starting array: [1, 1], 
Sum of elements of starting array = 2, putting sum on index = 0, array becomes: [2, 1],

Sum of elements of new array =  3, putting sum on index = 1. array becomes: [2, 3], which is equal to target array, hence the answer is 1.

In the second test case, 

It is impossible to create the target array from [1, 1, 1], hence the answer is 0.
Sample Input 2:
2
4
4 1 1 7
1
2
Sample Output 2:
1
0
Hint

Can you think of creating all the possible arrays from an array with all 1’s?

Approaches (2)
Recursion

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.
Time Complexity

O(N * (N ^ (K / N))), where ‘N’ is the number of elements in the target array and ‘K’ is the maximum element in the target array.

 

We are placing the sum value at all ‘N’ positions of the array and we are doing this recursively. The maximum height of the recursion tree will be (K / N) and it takes O(N) time to iterate through one array.  So the time complexity will be O(N * (N ^ (K / N))).

Space Complexity

O(N * (N ^ (K / N))), where ‘N’ is the number of elements in the target array and ‘K’ is the maximum element in the target array.

 

Since we are using arrays in every recursive call and also a recursion stack is used for recursion, the space complexity is O(N * (N ^ (K / N))).

Code Solution
(100% EXP penalty)
Create Target Array
Full screen
Console