Skip to content

Files

Latest commit

 

History

History
200 lines (159 loc) · 6.5 KB

File metadata and controls

200 lines (159 loc) · 6.5 KB
comments difficulty edit_url rating source tags
true
Hard
2383
Weekly Contest 198 Q4
Bit Manipulation
Segment Tree
Array
Binary Search

中文文档

Description

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 = 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

 

Constraints:

  • 1 <= arr.length <= 105
  • 1 <= arr[i] <= 106
  • 0 <= target <= 107

Solutions

Solution 1: Hash Table + Enumeration

According to the problem description, we know that the function f u n c ( a r r , l , r ) is actually the bitwise AND result of the elements in the array a r r from index l to r , i.e.,

Unable to render expression.

$arr[l] &amp; arr[l + 1] &amp; \cdots &amp; arr[r]$
.

If we fix the right endpoint r each time, then the range of the left endpoint l is [ 0 , r ] . Since the sum of bitwise ANDs decreases monotonically with decreasing l , and the value of a r r [ i ] does not exceed 10 6 , there are at most 20 different values in the interval [ 0 , r ] . Therefore, we can use a set to maintain all the values of

Unable to render expression.

$arr[l] &amp; arr[l + 1] &amp; \cdots &amp; arr[r]$
. When we traverse from r to r + 1 , the value with r + 1 as the right endpoint is the value obtained by performing bitwise AND with each value in the set and a r r [ r + 1 ] , plus a r r [ r + 1 ] itself. Therefore, we only need to enumerate each value in the set, perform bitwise AND with a r r [ r ] , to obtain all the values with r as the right endpoint. Then we subtract each value from t a r g e t and take the absolute value to obtain the absolute difference between each value and t a r g e t . The minimum value among them is the answer.

The time complexity is O ( n × log M ) , and the space complexity is O ( log M ) . Here, n and M are the length of the array a r r and the maximum value in the array a r r , respectively.

Similar problems:

Python3

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ans = abs(arr[0] - target)
        s = {arr[0]}
        for x in arr:
            s = {x & y for y in s} | {x}
            ans = min(ans, min(abs(y - target) for y in s))
        return ans

Java

class Solution {
    public int closestToTarget(int[] arr, int target) {
        int ans = Math.abs(arr[0] - target);
        Set<Integer> pre = new HashSet<>();
        pre.add(arr[0]);
        for (int x : arr) {
            Set<Integer> cur = new HashSet<>();
            for (int y : pre) {
                cur.add(x & y);
            }
            cur.add(x);
            for (int y : cur) {
                ans = Math.min(ans, Math.abs(y - target));
            }
            pre = cur;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        int ans = abs(arr[0] - target);
        unordered_set<int> pre;
        pre.insert(arr[0]);
        for (int x : arr) {
            unordered_set<int> cur;
            cur.insert(x);
            for (int y : pre) {
                cur.insert(x & y);
            }
            for (int y : cur) {
                ans = min(ans, abs(y - target));
            }
            pre = move(cur);
        }
        return ans;
    }
};

Go

func closestToTarget(arr []int, target int) int {
	ans := abs(arr[0] - target)
	pre := map[int]bool{arr[0]: true}
	for _, x := range arr {
		cur := map[int]bool{x: true}
		for y := range pre {
			cur[x&y] = true
		}
		for y := range cur {
			ans = min(ans, abs(y-target))
		}
		pre = cur
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

TypeScript

function closestToTarget(arr: number[], target: number): number {
    let ans = Math.abs(arr[0] - target);
    let pre = new Set<number>();
    pre.add(arr[0]);
    for (const x of arr) {
        const cur = new Set<number>();
        cur.add(x);
        for (const y of pre) {
            cur.add(x & y);
        }
        for (const y of cur) {
            ans = Math.min(ans, Math.abs(y - target));
        }
        pre = cur;
    }
    return ans;
}