Find a Value of a Mysterious Function Closest to Target
The function is defined as func(arr, l, r) = arr[l] AND arr[l+1] AND ... AND arr[r] — the bitwise AND of all elements of arr between indices l and r inclusive.
Winston was given the above mysterious function func. He has an integer array arr and an integer target, and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.
Return the minimum possible value of |func(arr, l, r) - target|.
Notice that func should be called with the values l and r where 0 <= l, r < arr.length.
Example 1
Input
arr = [9,12,3,7,15], target = 5Output
2The closest values produced by calling
func over all possible pairs are 7 and 3, so the minimum difference from 5 is 2.Example 2
Input
arr = [1000000,1000000,1000000], target = 1Output
999999Calling
func with all possible values of [l, r] always gives 1000000, so the minimum difference is 999999.Constraints
- 1 <= arr.length <= 10^5
- 1 <= arr[i] <= 10^6
- 0 <= target <= 10^7