A subarray is considered compromised if the bitwise OR of all elements in any subarray is present in the subarray itself. Find the number of compromised subarrays in a given array of positive integers.
A subarray is defined as any contiguous segment of the array.
Example arr = [2, 4, 7] Answer = 5
Please help with the processing idea?
More Questions: Given an alphabet of size m, find the number of passwords of length n such that no character appears k or more times consecutively.(hard)
Given a graph, perform DFS traversal and output all distinct valid outputs (such as all unique DFS traversal paths or orders depending on the specific constraint). (Medium)








First thing is observe a fact that if you OR two numbers the value increases or stays the same if they are equal. For each index i, you need to find a range [L,R] where there are no bad bits in reference to a[i] , meaning a bit is zero in a[i] but not in the range [L,R], if there is a bad bit , OR won’t be equal to a[i], you also need when a[i] appears again in the list to avoid duplicate counting, let’s assume a[k] is same as a[i] and k <=R, if so we’ll count all sub arrays that start from L or after, end between i and k-1 inclusive , if there is no such k then you count ending up to R from i. This you would do for range 1 to n and sum it up
i dont think stack would work
i think maintain prefix array bitwise means prefix[i][j] tells cnt of numbers upto index which have jth bit set
now for finding l,r you should do binary search like for sets all unset bits B in a[i] prefix[i][B] should be same as prefix[r][B]
i hope you understood
Find the nearest element to the left and right of each element, which has a bit which is set while the same bit is unset in our concerned number. You can use a monotonic stack for that.
Then, for each element, it's just subarray combinations keeping the central element. For same element occuring in one of these extensions, subtract accordingly
i dont think stack would work check my soln above and tell
The most effortless solution i can think is by using segment tree. Let's say ith element is OR of the some subarray then we can find the lower and upper bound. We can do binary search in Segment Tree, we are able to do this because we know doing prefix OR is always monotonically increasing.
ok
subarray [2, 1] is not a valid subarray
ohh got it... thanks a lot buddy!!
for P1,
maintain a array for storing the most recent index the bit 'b' is on this, way you will find the L and similarly find the R as well.
L = max(bit_prefix[i], L) where i is ith bit where the current index bit is off.
R = min(bit_sufix[i], R), where i is ith bit where the current index bit is off.