2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What's the context where you encountered this task? Can you credit the original source? $\endgroup$
    – D.W.
    Commented Aug 20, 2021 at 18:16

2 Answers 2

1
$\begingroup$

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

$\endgroup$
2
  • $\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$ Commented Aug 21, 2021 at 6:49
  • $\begingroup$ I will find the largest $j$ which satisfies the constraints. $\endgroup$ Commented Aug 21, 2021 at 11:37
0
$\begingroup$

Keep track of the and of a0 to a3, a4 to a7, a8 to a11 etc, a0 to a7, a8 to a15 etc, a0 to a15, a16 to a31 etc. This lets you calculate the and of any subarray in O(log n).

Find the first a(I) >= k. Find the largest j such that the and of a(I) to a(j) is >= k. This may be optimal. If a(j) < k then look for the next a(I) > k and try again.

If a(j) >= k then use your tables to find the smallest a(I) making the and >= k. This takes O(log (j-i)) time only. As an optimisation you can skip this step if a(j) and a(j+1) < k because you can’t get a subranges longer than the previous longest one.

$\endgroup$

Your Answer

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

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