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?

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

1 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)$.

  • $\begingroup$ Can you tell what will will you do once we find 1st 'i' for which & is >=k. It will be great if you can walk through a example. $\endgroup$ Aug 21, 2021 at 6:49
  • $\begingroup$ I will find the largest $j$ which satisfies the constraints. $\endgroup$ Aug 21, 2021 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.