saketag007's blog

By saketag007, history, 3 weeks ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How did you binary search for the answer?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well i ran a loop over the array , through which i fixed the loop variable , so my one end the subarray got fixed and the other end i found through binary search !