You are given an integer array \(A\) consisting of \(N\) elements. Your task is to determine for every element if any of its powers can be expressed as the sum of any subset of array \(A\).
Let \(S\) be any subset of \(A\).
\(\displaystyle\sum_{i=1}^{S.size()} S_i = A[i]^K\) where \(K \geq 2\).
See sample for a better explanation.
If it is possible to do for any element, print 1. Otherwise, print 0.
Input format
- The first line contains \(T\) denoting the number of test cases.
- The first line of each test case contains an integer \(N\) denoting the number of elements in array \(A\).
- The second line of each test case contains \(N\) space-separated integers of array \(A\).
Output format
For each test case, print a single line of \(N\) space-separated integers \((0/1)\). Print 0 if there is no subset such that the sum of that subset is equal to any power greater than 1 of the element at this index. Otherwise, print 1.
Constraints
\(1 \leq T \leq 5\)
\(1 \leq N \leq 100\)
\(1 \leq A[i] \leq 100 \forall i \in [1,N]\)
Let us consider answers for each index:
1st index: If we choose subset {1} of the array we know 12 =1 so answer for this index is 1 because element at this index 1 can be expressed. Note that we could also choose higher power.
2nd index: If we choose subset {3,5} of the array we know 23 =8 so answer for this index is 1.
Note that we could also choose power 2 and have set {4} or {1,3}.
3rd index: If we choose subset {1,8} of the array we know 32 =9 so answer for this index is 1.
8th index: There is no subset of array which equals 82,83 or higher powers so answer for this case is 0.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor