leetcode 1521 Find a Value of a Mysterious Function Closest to Target 与运算

题目

https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/

思路

与运算特性,只会递减,其中只会出现 1 变成 0
所以,以 r 为边界的 func 最多只会有 32 种结果,即从全1开始每次只少一个1,在此基础上遍历 r in [1,n]

源码

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        set<int> s;
        int mn = INT_MAX;
        s.insert(arr[0]);
        for(int i = 1;i < arr.size();++i){
            set<int> t;
            for(auto p:s){
                t.insert(p&arr[i]);
            }
            t.insert(arr[i]);
            s = t;
            for(auto p:s){
                //cout << p<<endl;
                mn = min(abs(p-target),mn);
            }
            //cout <<endl;
        }
        return mn;
    }
};