Finding subarray with target bitwise AND value

Question

Given an array A of size N and an integer P, find the subarray B = A[i...j] such that i <= j, compute the bitwise value of subarray elements say K = B[i] & B[i + 1] & ... & B[j].
Output the minimum value of |K-P| among all possible values of K.

Answer 1

Are you familiar with the Find subarray with given sum problem? The solution I'm proposing uses the same method as in the efficient solution in the link. It is highly recommended to read it before continuing.

First let's notice that the longer a subarray its K will be it will be smaller, since the & operator between two numbers can create only a smaller number.

So if I have a subarray from i to j and I want want to make its K smaller I'll add more elements (now the subarray is from i to j + 1), if I want to make K larger I'll remove elements (i + 1 to j).

If we review the solution to Find subarray with given sum we see that we can easily transform it to our problem - the given sum is K and summing is like using the & operator, but more elements is smaller K so we can flip the comparison of the sums.

This problem tells you if the solution exist but if you simply maintain the minimal difference you found so far you can solve your problem as well.

Edit

This solution is true if all the numbers are positive, as mentioned in the comments, if not all the numbers are positive the solution is slightly different.

Notice that if not all of the numbers are negative, the K will be positive, so in order to find a negative P we can consider only the negatives in the algorithm, than use the algorithm as shown above.