You are visiting a fair in byteland. You are shopping and want to buy Q items. Each item cost exactly B[i] amount of money. You have no money but you have a magical bag on which you can apply an operation any times you want. In bag there are N integers denoted by array A. In one operation, You choose two integer X Y from A and deposit all of the amount of money M you have, this will magically increase your money by X ⊕ Y. Note: You have to deposit all money you have otherwise you will be exiled from Byteland for your greed. Also, shopkeepers have no change, So you have to pay exact amount. :p Treating each item as independent and starting with 0 amount of money, Can you find if we can buy each item?
Problem Constraints
2 ≤ N ≤ 1000
1 ≤ A[i] ≤ 10000
1 ≤ Q ≤ 100000
0 ≤ B[i] ≤ 10^9
Input Format
First argument contains an integer array A of size N. Second argument contains an integer array B of size Q.
Output Format
Return a binary string of size Q containing i as 1 if its possible to buy ith item else 0.
Example Input
Input 1:
A = [1, 2], B = [3, 5, 10, 15]
Input 2:
A = [1, 2, 3], B = [1, 5, 10]
Example Output
Output 1:
"1001"
Output 2:
"111"
My approach : As N is only 1000 we can generate all possible xor pairs whose value will not exceed the maximum possible value of array element (i.e.10000). Let's store all the xor values from all possible pairs in another array XOR_ARRAY. After this for each query we basically need to find if there exists some subset in the XOR_ARRAY whose sum is equal to the required value. Seems like subset sum problem but constraints are large so I am stuck here.
Please let me know if I am thinking in correct way or is there some other approach to solve this problem. Thanks in advance :)
I wrote a comment with a solution, can you share the problem source? If you do so I can post it.
This is from Interviewbit codedrift graphs.
Thank you for sharing the problem, I quite like it :D tell me if the editorial proves the solution complexity or if it just accepts it as being fast enough due to optimizations.
Alright here's my solution:
First of all, "After this for each query we basically need to find if there exists some subset in the XOR_ARRAY whose sum is equal to the required value" is not accurate. You can repeat elements.
Second of all, xor of elements might be greater than the maximum value (but they can't have higher bits set on).
If we remove repeated elements from A, you can prove that the smallest pair xor will be O(maxValue / N). To prove this, think about highest bits being 1 or 0 in this number then use the pidgeonhole principle.
Let's call that smallest value X. If we have some number Y, then we can get all Y + k * X, so we just care about the first number we can generate for each value mod X (discard greater numbers). This turns into a shortest path problem. Using dijkstra, it's O(E * logV) = O((X * min(N^2, X)) * logX) = O(maxValue / N * min(N^2, maxValue / N) * logX) = O(min(maxValue^2/N^2, N*maxValue) * logX). Worst case happens when N is around maxValue^(1/3) if we ignore logX in the optimization step, so this last part (the graph part) is O(maxValue^(4/3) * logX), to construct this we still need to do O(N^2) work or use xor convolution to get clean O(maxValue^(4/3) * log(maxValue)) algorithm if we take log(maxValue/N) = O(log(maxValue)).
There's probably a simpler solution though?
Pidgeon idea is amazing! :)
Just to make it clear to other people that didn't understand:
First, let's remove repeated elements from A if there are any. Let's call the largest number possible M and let's round that up to the closest power of 2, so M = (2^B)-1. The highest bit that appears in numbers is the 2^(B-1) bit
Now, when is the smallest pair xor guaranteed to not have the highest bit? When there's a pair where the highest bit is the same! So if N > 2, then by the pidgeon-hole principle, there's a pair that has xor without the highest bit.
More generally, if N > 2^X, then the smallest pairwise xor doesn't have the X highest bits. Since that X is basically log2(N-1), then the smallest pair xor is O(M / 2^(log2(N-1))) = O(M / N)
Here's a similar idea to tfg's solution:
Let's say the number of distinct integers in A is X. Let S be the set of the distinct integers you get after xor'ing all pairs in A.
Furthermore, let Y be the floor of log(X — 1) (base 2). Assume Y >= 1 (we can special case X = 1 pretty easily. X = 2 is also pretty easy using either brute force or postage stamp problem solution.)
Notice that the smallest number in S will be at most 16384 / 2^Y (pigeonhole principle). Furthermore, the second smallest number will be at most 16384 / 2^(Y-1).
Thus, we only need to check numbers less than 2^28 / (2^(2Y) — 1) by postage stamp problem solution (its a less less than that, sure, but it doesn't really matter).
You can do this just with a DP; it shouldn't be too bad. You should get around 2^28 operations worst case, but the operations are very simple and cache-optimized, so it should be OK. Also, you won't get MLE because it's a bool array.
One thing that I don't understand: what's the "postage stamp problem" you're talking about? If I google that name I find something that doesn't seem related.