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

Question

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?

Answer 1

Suppose that $A$ has length $n$, and let $m$ be the midpoint. Partition your array into two parts: $A_1 = A[1],\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[1] \& \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)$.