1521. Find a Value of a Mysterious Function Closest to Target

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.

c++

class Solution {
    int seg[400000];
    void update(int u, int s, int e, int l, int r, int v) {
        if(r < s or e < l) return;
        if(l <= s and e <= r) {
            seg[u] = v;
            return;
        }
        int m = (s + e) >> 1;
        update(u * 2, s, m, l, r, v);
        update(u * 2 + 1, m + 1, e, l, r, v);
        seg[u] = seg[u * 2] & seg[u * 2 + 1];
    }
    
    int query(int u, int s, int e, int l, int r) {
        if(r < s or e < l) return INT_MAX;   
        if(l <= s and e <= r) return seg[u];
        int m = (s + e) >> 1;
        return query(u * 2, s, m, l, r) & query(u * 2 + 1, m + 1, e, l, r);
    }
    int bs(int l, int r, int n, int& t) {
        int res = INT_MAX;
        int s = l, e = r;
        while(l < r) {
            int m = (l + r + 1) / 2;
            int q = query(1, 1, n, l, m);
            if(q >= t) l = m;
            else r = m - 1;
        }
        res = min(res, abs(t - query(1,1,n, s,l)));
        if(l + 1 <= n)
            res = min(res, abs(t - query(1,1,n,s,l+1)));
        if(l - 1 >= s)
            res = min(res, abs(t - query(1,1,n,s,l-1)));
        return res;
        
    }
public:
    int closestToTarget(vector<int>& arr, int target) {
        int n = arr.size(), l = 1, r = n, res = INT_MAX;
        for(int i = 0; i < n; i++) {
            update(1, 1, n, i + 1, i + 1, arr[i]);
        }
        
        for(int i = 1; i <= n; i++)
            res = min(res, bs(i,n,n,target));
        
        return res;
    }
};

• ternary search solution

c++

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O3")
int seg[400000];

class Solution {
    void update(int u, int s, int e, int l, int r, int v) {
        if(r < s or e < l) return;
        if(l <= s and e <= r) {
            seg[u] = v;
            return;
        }
        int m = (s + e) >> 1;
        update(u * 2, s, m, l, r, v);
        update(u * 2 + 1, m + 1, e, l, r, v);
        seg[u] = seg[u * 2] & seg[u * 2 + 1];
    }
    
    int query(int u, int s, int e, int l, int r) {
        if(r < s or e < l) return INT_MAX;   
        if(l <= s and e <= r) return seg[u];
        int m = (s + e) >> 1;
        return query(u * 2, s, m, l, r) & query(u * 2 + 1, m + 1, e, l, r);
    }
    int ternarySearch(int l, int r, int n, int t) {
        int s = l;
        int res = min(abs(t - query(1,1,n,s,l)), abs(t-query(1,1,n,s,r)));
        while(l + 3 <= r) {
            int p = (l * 2 + r) / 3, q = (l + r * 2) / 3;
            int qq = query(1, 1, n, s, q), qp = query(1, 1, n, s, p);

            qp = abs(qp - t);
            qq = abs(qq - t);
            res = min({res, qq, qp});
            if(qp < qq) l = p;
            else r = q;
        }
        for(int i = l; i <= r; i++)
            res = min(res, abs(query(1,1,n,s,i) - t));
        return res;
    }
public:
    int closestToTarget(vector<int>& a, int target) {
        int n = a.size(), l = 1, r = 1, res = INT_MAX;
        for(int i = 1; i < n; i++) {
            if(a[i] == a[r-1]) continue;
            a[r++] = a[i];
        }
        
        for(int i = 0; i < r; i++) {
            update(1, 1, r, i + 1, i + 1, a[i]);
        }
        
        for(int i = 1; i <= r; i++)
            res = min(res, ternarySearch(i,r,r,target));
        
        return res;
    }
};