1
$\begingroup$

A sequence is good if the bitwise AND of all its elements is a perfect square.

So counting number of "good" sequences, in a subarray .
For example : in [1, 2, 3]
There are 6 sub-sequences:

enter image description here

So there are 3 "good" sequences
Can you suggest an efficient approach to count them ?

$\endgroup$
1
$\begingroup$

Take random 64 bit integers. What are the chances that the AND of the first ten has more than one bit set? So for random numbers, I’d say the count is close to n^2 / 2, and it takes cn operations for small n to count them all.

If $x=0$ or $x=4^k$ then x is a square, and x AND y is a square for any y. So if the AND of the first five numbers for example is one of these squares, then the AND of the first six, seven, eight, ..., n numbers is a square. Here's a simple algorithm:

total = 0
for 1 ≤ i ≤ n
    x = (all bits set)
    for i ≤ j ≤ n
        x = x AND a[j]
        if x = 0 or x = 4^k for some k
            total += n - j + 1
            break from for loop for j
        else if x is a square
            total += 1

This works well when the numbers are random. To improve for the worst case (for example alternating between 2 and 3, where this simple algorithm would take quadratic time), calculate the AND of groups of 2, 4, 8, 16, 32 etc. numbers, and observe that when calculating the AND of say a million 64 bit numbers, there will only be 64 different values. This is slightly complicated but not hard to implement if you are really interested in the solution.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Let the sequence be $a_1,\cdots,a_n$, and let $A_{i,j}=a_i\text{ and }\cdots\text{ and }a_j$. Assume each $a_i$ has at most $w$(e.g. $w=32$) bits. Fix $i$ and let $j\geq i$ varies, $A_{i,j}$ has at most $w'\leq w+1$ different possible values $A_{i,j_1},\cdots,A_{i,j_{w'}}$. For each distinct value we record the leftmost $j$ that generates it.

In $O(w)$ time we can compute the set of distinct values (as well as the corresponding range of $j$) of $A_{i-1,j}$ from $A_{i,j}$. Using this observation, we should be able to find an $O(nw)$ time algorithm.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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