<p><img alt="" src="https://assets.leetcode.com/uploads/2020/07/09/change.png" style="width: 635px; height: 312px;" /></p>

<p>Winston was given the above mysterious function <code>func</code>. He has an integer array <code>arr</code> and an integer <code>target</code> and he wants to find the values <code>l</code> and <code>r</code> that make the value <code>|func(arr, l, r) - target|</code> minimum possible.</p>

<p>Return <em>the minimum possible value</em> of <code>|func(arr, l, r) - target|</code>.</p>

<p>Notice that <code>func</code> should be called with the values <code>l</code> and <code>r</code> where <code>0 &lt;= l, r &lt; arr.length</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [9,12,3,7,15], target = 5
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [1000000,1000000,1000000], target = 1
<strong>Output:</strong> 999999
<strong>Explanation:</strong> Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [1,2,4,8,16], target = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= arr[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>0 &lt;= target &lt;= 10<sup>7</sup></code></li>
</ul>

#define ll long long
class Solution {
private:
    ll findOR(ll l, ll r, vector<vector<ll>> &pref){
        ll OR = 0ll;
        for(ll i=0; i<32; i++){
            ll val1 = (l > 0)? pref[l-1][i] : 0;
            ll val2 = pref[r][i];

            if(val2 - val1 == (r - l + 1)){
                OR += (1 << i);
            }
        }
        return OR;
    }
public:
    int closestToTarget(vector<int>& nums, int target) {
        // The only reason why i was using segment tree was that i wanted to have
        // the AND of a subsegement in logN time or say o(1) time

        // but it can also be calculated using prefix sum on 2D Arrays

        // HOW?
        // if for each index i maintain an array of size = 32
        // where there is the cumulative bits of all the numbers starting from index 0
        // then i can somehow in O(1) only comment about the bitwise and of the subsegment [l -> r]

        // The main logic remains same
        // go to each index and treat it as the starting element of the subarray
        // now usin BS find the index of the element of the such that the cumulate or between the index L and the mid(from BS) is minimum
        // we know that this is monotonic function coz
        // if the cumulative OR comes out to be > target, in that case all the eleents before it would be having the cumulative or greater than target
        // if the cumulative OT comes out to be < target, in that case all the elements after it would be always less than the cumulative or
        // Now ofcourse after each BS iteration i would eant a number more closer to k, thus in both case we change our lo and hi pointer to respective positions

        // if(val > target) lo = mid + 1 increase the array (length wise).
        // if(val < target) hi = mid - 1 decrease the array (length wise).

        ll n = nums.size();
        ll ans = 1e9;

        // Making the prefix vector
        vector<vector<ll>> pref(n, vector<ll> (32, 0));
        vector<ll> first(32, 0);
        for(ll i=0; i<32; i++){
            if(nums[0] & (1 << i)) first[i] = 1;
        }
        pref[0] = first;

        for(ll i=1; i<n; i++){ 
            for(ll j=0; j<32; j++){
                pref[i][j] = pref[i-1][j];
                if(nums[i] & (1 << j)) pref[i][j] += 1;
            }
        }

        // O(N)
        for(ll L = 0; L < n; L++){
            ll lo = L;
            ll hi = n - 1;
            // O(logN)
            while(lo <= hi){
                ll mid = ((lo + hi) >> 1);
                // This is simply a O(1) operation
                ll cumulativeOR = findOR(L, mid, pref);

                ans = min(ans, abs(target - cumulativeOR));

                if(cumulativeOR > target){
                    lo = mid + 1;
                }
                else{
                    hi = mid - 1;
                }
            }
        }

        // Overall TC -> O(NlogN)

        return ans;
    }
};
278000