# Find maximum length subarray whose bitwise AND is at least $k$ in $o(n^2)$

Given an array $$A$$ of unsigned integers, a subarray is a contiguous interval $$A[\ell],\ldots,A[r]$$. The bitwise AND of the subarray is just the bitwise AND of $$A[\ell],\ldots,A[r]$$ (what is denoted by A[l] & ... & A[r] in C).

I am faced with the following task:

Given an array and an integer $$k$$, find the maximum length of a subarray whose bitwise AND is at least $$k$$.

The intended running time is $$o(n^2)$$, but I can only think of $$O(n^2)$$ solutions. How do I get below quadratic running time?

• What is a bitwise AND of a single array? Did you mean to do a bitwise AND of the subarray with something? Aug 20, 2021 at 12:48
• I have edited the comment. Please see the definition now. Aug 20, 2021 at 12:50
• What's the context where you encountered this task? Can you credit the original source?
– D.W.
Aug 20, 2021 at 18:16

Suppose that $$A$$ has length $$n$$, and let $$m$$ be the midpoint. Partition your array into two parts: $$A_1 = A,\ldots,A[m]$$ and $$A_2 = A[m+1],\ldots,A[n]$$. Any solution must either lie entirely in $$A_1$$, entirely in $$A_2$$, or must consist of a suffix of $$A_1$$ and a prefix of $$A_2$$. This suggests a recursive algorithm which recurses on $$A_1$$ and on $$A_2$$, and then needs to find the maximum length of a subarray AND'ing to at least $$k$$ which consists of a suffix of $$A_1$$ and a prefix of $$A_2$$.
For the latter task, we first compute the ANDs $$A[m], A[m-1] \& A[m], \ldots, A \& \cdots \& A[m],$$ storing them aside. Now we find the first $$i$$ (if any) such that $$A[i] \& \cdots \& A[m] \geq k$$. We find the maximum $$j \geq m$$ such that $$A[i] \& \cdots \& A[j] \geq k$$. This gives us a candidate subarray. Now we increment $$i$$, and advance $$j$$ to the maximum position satisfying $$A[i] \& \cdots \& A[j] \geq k$$, giving us another candidate; here we are crucially using the property $$x \& y \leq x$$, which guarantees that the maximal $$j$$ is a monotone function of $$i$$. We continue incrementing $$i$$ in this way until we have processed $$i = m$$. At this point, we have checked all maximum length subarrays straddling the midpoint $$m$$.
This divide-and-conquer algorithm runs in $$O(n\log n)$$.
• I will find the largest $j$ which satisfies the constraints. Aug 21, 2021 at 11:37