Find the bitwise AND of a subarray closest to given number
Let f (i, j) = AND ($A_i, A_{i+1}, ..., A_{j-1})$ for $0 ≤ i &lt; j ≤ n$. $f (i, j)$ has the property that whenever $i ≤ i' &lt; j' ≤ j$, $f (i, j) ≤ f (i', j')$. 

We also have $f (i, j)$ = AND($(f (i, k), f (k, j)$) for any $0 ≤ i &lt; k &lt; j ≤ n$.

Because of these properties, we get an algorithm slightly better than brute force as follows: 

Keep track of the optimal solution so far, initialising with f (0, 1). For 0 ≤ i &lt; n: If $a_i ≤ P$ then check if f (i, i+1) is a better solution. Otherwise, find the largest j such that f (i, j) ≥ P; it may be that j = n. Check if f (i, j) is a better solution. If j &lt; n then check if f (i, j+1) &lt; P is a better solution.

How to find the largest j in O (log n), making the total time O (n log n): 

We start by building some tables, calculating all f (i, i+2) for even i, f (i, i+4) for i multiple of 4, f (i, i+8) for i multiple of 8. This is done in O (n) since there are about n values which can each be calculated with a single AND operation. 

To find the largest j, we start with j = i+1, f (i, j) = a [i]. If j &lt; n is odd then we can calculate f (i, j+1); if the result is ≥ P then we replace j with j+1, which makes j even. Then if j &lt; n is an odd multiple of 2 we can calculate f (i, j+2); if the result is ≥ P then we replace j with j+1, which makes j a multiple of 4, and so on. This ends with j being a multiple of $2^k$ for some k. Now we try to increase j by $2^{k-1}$, $2^{k-2}$, ..., 4, 2, 1 if the increased j is ≤ n, and f (i, j) ≥ P. The total cost is O (log n) operations.