Method

Let’s start by thinking about this problem:

Suppose $a[n]$ is an array of length $n$ with all its value non-negative integers. For each index $i$, find all the $AND$ value of the subarrays ending at $i$.

If given the problem occasionly or I don’t care about the efficiency😀 , I would iterate from $i$ to $0$ and calculate the $AND$ value along the way. This has $O(n^2)$ time complexity. But we do not utilize the property of $AND$ operation.

Another approach begins by the fact that $a[i], a[i] \& a[i-1], \cdots, a[i]\&\cdots \& a[1]\&a[0]$ is non-increasing. We may want to “stop” at some index to save time. Suppose we already know $a[i-1],a[i-1]\&a[i-2],\cdots, a[i-1]\& \cdots \& a[1] \& a[0]$ , if for some $j$ we have $a[i] \& (a[i-1] \& a[i- 2] \& \cdots \& a[i-j])=a[i-1] \& a[i- 2] \& \cdots \& a[i-j]$, we do not need to go further since “AND” will not decrease the value any further.

We find the ${k: a[i] \& a[i-1] \& a[i- 2] \& \cdots \& a[i-k] < a[i-1] \& a[i- 2] \& \cdots \& a[i-k]}$
has at most $\text{numBits}(a[i])$, which could be upper bounded by $\log_2 a[i]$. This is because $a[i]$ has bit $0$ while $a[i-1]\&\cdots\& a[i-k]$ has 1 at some bit. The positions of such bits in different $k$ are also different, given the monotonicity of AND operation.

Hence the whole algorithm gives $O(n\log_2 \max(a))$ time complexity. This is actually a huge improvement, we need $a=2^n$ to degenerate to the brute force case. Now imagine we have a $10^3$ length array, the running time gaurantee becomes quadratic in $n$ with $2^{1000}=1995\cdots76$, which contains 3011 digits !

In implementation, we will use the in-place modification trick, i.e. to store the information of $a[i-1]\& a[i-2] \&\cdots \& a[k]$ $(k\leq i-1)$ in the original array, intuitively we can visualize the process in the table below, and I write an example python script to further show a prototype for logTrick.

a = [10, 2, 4, 6, 8, 6]  
n = len(a)  
for i in range(n):  
    x = a[i]  
    for j in range(i - 1, -1, -1):  
        if x & a[j] == a[j]:  
            break  
        a[j] &= x
    print(a[:(i+1)]) 

Note: the ‘print’ stuff is just for showcasing, adding it would lead to $O(n^2)$ time complexity. Usually we do not want all the subarray AND values to be the output but instead use some properties of them.

References

[1] https://zhuanlan.zhihu.com/p/1933215367158830792 LogTrick入門教程

[2] https://leetcode.cn/problems/minimum-sum-of-values-by-dividing-array/solutions/2739258/ji-yi-hua-sou-suo-jian-ji-xie-fa-by-endl-728z/