#1521
Find a Value of a Mysterious Function Closest to Target
candidate master · 1505 · lc hard +32 · verified · 47.1% accepted · 404 likes · top 32%
Description
Given an integer array arr and an integer target, the mysterious function func(arr, l, r) computes the bitwise AND of arr[l..r]. Over all valid pairs 0 <= l <= r < arr.length, return the minimum value of |func(arr, l, r) - target|.
Example 1:
Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.
Example 2:
Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.
Example 3:
Input: arr = [1,2,4,8,16], target = 0
Output: 0
Code
1
2
3