Given an array A of size n and a target integer X, we need to find an array B such that ΣA[i]&B[i]=X (1<=i<=n).
If multiple answers are possible find the lexicographically smallest array B.
As constraints are unknown, I hope someone can help me to find suitable constraints too.
Can you give me more informations ?
a[i] <= ? b[i] <= ? n <= ?
He said constraints are unknown
Ahh, sorry I really didn't notice that. :)
This problem is a kind of knapsack problem with restoring the path from the end..
Let maxValue maximum b[i] , b[i] <= maxValue
My solution with DP.
Time complexity will be O(n * x * maxValue) .
Let : N <= 100 , maxValue <= 100 , x <= 10000
bool dp[N][maxValue * N] ;
Our DP state will be dp[i][sum] ;
Initially dp[0][0] = 1 , because to get sum 0 is always available.
dp[i][sum] -> means Can we get prefixSum j on prefix I ?
Transitions: dp[i][sum] |= dp[i — 1][sum — (j & a[i])] ; Here j means the value we can put as a b[i]
if (dp[n][x] == 0) then answer = -1 ;
else you can restore the dp path from end , and you can add j value to array b .
SORRY FOR BAD ENGLISH
Hi, haven't thought about it much but this should probably work.
In the optimal answer, all $$$B[i]$$$s are sub-masks of their $$$A[i]$$$s.(If they aren't, the sum won't change by setting the extra '1' bits to '0's leading to a better answer and hence, a contradiction) Store the bits in a frequency array for all $$$A[i]$$$. If they can't make $$$X$$$, then impossible. Else: Assign each $$$b[i]$$$ greedily from the first to last(to get lexicographical smallest). For each $$$b[i]$$$, set the bits greedily from HSB to LSB. Basically, check if it is still possible to get $$$X$$$ with the remaining bits assuming the current bit is set to $$$0$$$, if not, then it must be set to $$$1$$$ and remove that from $$$X$$$. Checking if a frequency array of $$$log(X)$$$ bits can make $$$X$$$ is easy to do in $$$O(log(X))$$$ by checking from LSB to HSB and transferring bits to higher bit $$$(2^a = 2^{a-1} * 2)$$$ depending on if current bit in $$$X$$$ is $$$0/1$$$.
Complexity: $$$O(Nlog(X)^2)$$$. A $$$log(X)$$$ factor could probably be shaved off.