Can you give me more informations ?

a[i] <= ? b[i] <= ? n <= ?

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]

dp[0][0] = 1 ;
rep(i, 1, n) {
    rep(sum, 0, x) {
        rep(j, 0 , maxValue) { // -> j is = new b[i]
            if (sum >= (j & a[i])) {
                dp[i][sum] |= dp[i - 1][sum - (j & a[i])] ;
            }
        }
    }
}
if (dp[n][x] == 0) {
    cout << "No solution" ;
} else {
    // Restore the path from the end
}

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.