1521

1521. Find a Value of a Mysterious Function Closest to Target (Hard)

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 <= 10^5
• 1 <= arr[i] <= 10^6
• 0 <= target <= 10^7

Related Topics:
Binary Search, Bit Manipulation, Segment Tree

Solution 1. Brute force

The func funciton is calculating the result of applying bitwise and operation on all the elements between arr[l] and arr[r] inclusive.

Note that when we apply bitwise and operation from left to right, the result value is monotonically decreasing since whenever a bit 0 is met, that bit will no longer be set back to 1.

So we can have two insights:

• Once the result is 0, we don't need to continue calculating more elements.
• We only need to keep calculating if the and result is greater than or equal to target because:
  • If the result is greater than or equal to target, we can keep calculating the result since decreased result will get closer to target.
  • If the result is less than target, we don't need to continue calculating because the difference between it and the target will only increase.

// OJ: https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int closestToTarget(vector<int>& A, int target) {
        int N = A.size(), ans = INT_MAX;
        for (int i = 0; i < N; ++i) {
            if (i > 0 && A[i] == A[i - 1]) continue;
            int func = A[i];
            ans = min(ans, abs(func - target));
            for (int j = i + 1; j < N && func && func >= target; ++j) {
                func &= A[j];
                ans = min(ans, abs(func - target));
            }
            if (ans == 0) return 0;
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int closestToTarget(vector<int>& A, int target) {
        int N = A.size(), ans = INT_MAX;
        for (int i = 0; i < N; ++i) {
            if (i > 0 && A[i] == A[i - 1]) continue;
            int func = A[i];
            for (int j = i; j < N; ++j) {
                func &= A[j];
                ans = min(ans, abs(func - target));
                if (func <= target) break;
            }
            if (func >= target) break; // if the result is greater than or equal to `target`, the best result we can get in the next loop must be greater than the current result, so the difference can only increase, we can break here.
        }
        return ans;
    }
};

Solution 2.

Note that using set is more performant than unordered_set here. It's because unordered_set initialization has greater overhead.

// OJ: https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/
// Author: github.com/lzl124631x
// Time: O(N(logM)^2) where M is the maximum element in A
// Space: O(logM)
// Ref: https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/discuss/743381/Python-6-lines-O(nlogm)-solution
class Solution {
public:
    int closestToTarget(vector<int>& A, int target) {
        set<int> s;
        int ans = INT_MAX;
        for (int n : A) {
            set<int> next{n};
            for (int m : s) {
                if ((m & n) < target) continue;
                next.insert(m & n);
            }
            for (int val : next) ans = min(ans, abs(val - target));
            if (ans == 0) return 0;
            swap(s, next);
        }
        return ans;
    }
};

Since there are only log(M) elements in the set, we can even use vector<int> to store the values.

// OJ: https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/
// Author: github.com/lzl124631x
// Time: O(N * logM * loglogM)
// Space: O(logM)
class Solution {
public:
    int closestToTarget(vector<int>& A, int target) {
        vector<int> s;
        int ans = INT_MAX;
        for (int n : A) {
            vector<int> next{ n };
            for (int m : s) {
                if ((m & n) < target) continue;
                next.push_back(m & n);
            }
            sort(begin(next), end(next));
            next.resize(unique(begin(next), end(next)) - begin(next));
            swap(s, next);
            ans = min(ans, abs(s.front() - target));
        }
        return ans;
    }
};