I have an array A and an integer P , find a subarray B = A[i,,,,j] , i<=j , compute bitwise '&' of all the numbers in the subarray which would be equal to K . I have to find the minimum value of |K-P| over all possible values of K.
Sample test case:-
3 2 // size of array and P
5 6 7 // elements of array
O/P — 2
We can take subarray [1,3] or [1,2] both have bitwise & to be '4' , so |K-P| = |4-2| = 2
My approach :- I built a segment tree doing bitwise & , so I could get the value 'K' of any subarray in log N time. Then i binary searched my appropriate answer!
My expected time complexity :- O(NlogN)
Could there be any faster or easier solution?