PROBLEM LINKS:
DIFFICULTY:
Medium
PREREQUISITES:
- Binary search
- Range queries without any updates (Segment tree/Sparse table/Fenwick Tree/etc.)
PROBLEM:
Given an array A of n integers & m queries.In every query an integer x is given.Let S be the set of all the subarrays S_{i} of array A such that the bitwise and of all elements in S_{i} results to x.Let |Si| represent number of elements in subarray S_{i}.
Your task is to find (\displaystyle\sum_{S_i \in S} \mid S_i \mid) for every query.
EXPECTED COMPLEXITY :
O(n.logn) / O(n.(logn)^{2})
DISCUSSED COMPLEXITY :
O(n.(logn)^{2})
CORE IDEA BEHIND THE PROBLEM :
Bitwise & of a number x is a non-increasing function & it can change only logx times at most.
EXPLANATION :
Let us solve simpler problem first.What if we only had to deal with prefix subarrays instead of all subarrays?
Let us take a random array a of integers.
a_{1} | a_{2} | a_{3} | a_{4} | ... | an |
x_{1}=a_{1} | x_{2}=x_{1}&a_{2} | x_{3}=x_{2}&a_{3} | x_{4}=x_{3}&a_{4} | ... | x_{n}=x_{n-1}&a_{n} |
Now,let us take an array x where x_{i} = bitwise & of all elements between index 1 & i. . It is obvious that x_{i+1}<=x_{i}.But the important thing to notice is that if x_{i+1} < x_{i}_{ },then the decrement(x_{i}-x_{i+1}) must be sum of powers of 2(some bits of x_{i }which were set(1),now they would be unset(0) in x_{i+1}).
Now,how many distinct x_{i} can we possibly have?
For maximum distinct x_{i} , we can suppose anytime x decreases,it decreases by a single power of 2 (only a single set bit of x_{i} becomes unset in x_{i+1}) & finally x_{n} becomes 0 (zero).So,maximum times value of x can decrease is equal to count of set bits in x_{1}.Hence,we can conclude that value of x can change at most log x_{1}(or say log a_{1})times.
Let us define a function f(i) which gives bitwise & of all elements between index 1 & i in O(1).
We can observe that f(i) is a non-increasing function i.e.it will either remain same or decrease with increasing i.So,binary search can be used to find i corresponding to some y=f(i). Binary search on a function (geeksforgeeks)
There will be many indice range for which x_{i} will remain same.So,we know x_{i} & we just have to find corresponding i.Suppose we are at index l & value of x is x_{l}. then we could binary search for last index r such that x_{l}=x_{l+1}=…=x_{r} in O(log(n-l+1)).Let us see how.
Let us define some things for ease of understanding:
f(i) : BItwise & of all elements between index 1 & i.
map<int,int> cnt
cnt[i] : how many subarrays have bitwise & value i.
``` int start=i,end=i; int l=start,r=n; while(l<=r) { int mid=(l+r)/2; if(f(mid)==f(start)) end=mid,l=mid+1; else r=mid-1; } cnt[f(start)]=(end-start+1); ``` Suppose we that are at index i.Let us call start=i. To find the right end (the last index end in the array such that f(start)==f(end) ),we use binary search as above.We fix the right end at index i only and start extending it to the right by using binary search on f(i). We take the range [start,n] into consideration and start dividing it further into smaller ranges.Ultimately,we find the rightmost index end such that f(start)==f(end) & no other index j>end exists which satisfies this condition.After finding the right end, we can say that all the subarrays (1,start),(1,start+1),...(1,end) have same bitwise & value which is f(start).Also we can say that (end-start+1) prefix subarrays(subarrays with left end at index 1) exist which have bitwise & value=f(start).So,cnt[f(start)]=(end-start+1). Now we can extend this solution to find all the distinct values that f(i) can take along with their start & end points in the following way:``` int start=1,end=1; while(start<=n) { int l=start,r=n; while(l<=r) { int mid=(l+r)/2; if(f(mid)==f(start)) end=mid,l=mid+1; else r=mid-1; } cnt[f(start)]=(end-start+1); start=end+1; end=start; } ``` We start at starting index 1.Then we try to find the right end for x_{1}.Suppose right end is at index end.Then,we know that f(1)=f(2)=...=f(end-1)=f(end).We increment our new starting index to end+1.New required x is f(start).Similarly,we find end points and continue this process till we reach the end. We know that f(i) can take at max log(a[1]) values.So start index will be updated log(a[1]) times.For every starting index,we do binary search to find the right end which takes log(n-start+1) time.We can see that the total complexity for calculating all prefix subarrays is (log(n))^{2}(avoiding exact values inside log).This solution is only for prefix subarrays. Now we further extend this for all subarrays.We declared start ing index as 1 in above code.Now,we would take every index in the array as starting index and follow the same process as above. f(i,j) : Bitwise & of all elements between index i & j. Note:For calculating f(i,j) we can use any datastructure which can query a range in O(1)/O(logn).Sparse table is used in my solution as it can answer a range query in O(1). map cnt,mp. cnt[i]-count of subarrays whose bitwise & value is i. mp[i]-sum of sizes of all subarrays whose bitwise & value is i.``` for(int i=1;i<=n;i++) { int start=i,end=i; while(start<=n) { int l=start,r=n; while(l<=r) { int mid=(l+r)/2; if(f(i,mid)==f(i,start)) end=mid,l=mid+1; else r=mid-1; } cnt[f(i,start)]=(end-start+1); int l1=start-idx,l2=end-idx+1; mp[cur]+=( ((l2*(l2+1))/2) ) - ( ((l1*(l1+1))/2) ); start=end+1; end=start; } } ``` We consider every index between 1 & n as the starting index.Calculation of mp[i] is just simple maths.Since we are calculating for entire array,new complexity is O(n.(logn)^{2}). SOLUTION LINK:
- Author's solution : Author's solution
- Tester's solution : Author's solution