Count numbers that can be generated by flipping bits according to position intervals

We have $M$ bits. $M\le10^5$ Also we have N ranges in the form $[L,R]$. $N\le10^5$ We can choose any range from the given ranges and flip all bits in our number from $L$ to $R$, both inclusive. We can apply each operation any number of times and in any order. We have to calculate the number of $M$ bit numbers that can be formed thus.

for Example if $N=3$ and our ranges are : $[0,0]$, $[1,1]$, $[2,2]$. Now if we need to find number of three bit numbers that can be formed using the above restrictions, our answer would be 8, since we can form everything from 0 to 7.

Example 2: if we have 3 bits and two ranges $[0,1]$, $[1,2]$, we can form $4$ distinct numbers : $0 (000)$, $3 (011)$, $6 (110)$ and $5 (101)$.

I was thinking of doing something like if we could just obtain the $i^{th}$ bit as $1$ after performing some operations we could simply take $2^X$ for all such bits and that many numbers can be formed. But this approach doesn't seem to work in general.

• What's the relevance of $M,N\leq 10^5$? Feb 8, 2014 at 15:57
• @DavidRicherby Limits imply anything above $O(N* log N)$ worst case will not be feasible. Feb 8, 2014 at 18:25
• An algorithm that took $N^2$ steps would be only around 10s of compute time on a 1GHz CPU. Feb 8, 2014 at 19:21
• @DavidRicherby For what it's worth, this appears to be a currently active competition problem on codechef.com with a time limit of one second.
– mhum
Feb 13, 2014 at 18:14

1 Answer

Hint: For given $N$ and a range $[L,H]$, let $v \in \mathbb{Z}_2^N$ be the characteristic vector of $[L,H]$, i.e. $v_i = 1$ if $L \leq i \leq H$ and $v_i = 0$ otherwise. Given a list of ranges $[L_j,H_j]$ and correspond vectors $v_j$, how can you represent the characteristic vectors of all numbers reachable by the operations you mention? What is the relevant parameter?

Another hint: What happens if all $L_i$ are distinct? How can you handle cases in which $L_i = L_j$ for some $i \neq j$? Try to reduce it to the former case.

• I can think of forming an N*N matrix with 1's for all [L,R] range for each row. And then maybe the rank of that matrix will be our answer? Rank in finite field 2. Feb 8, 2014 at 18:10
• Yes, that's the idea. Feb 8, 2014 at 18:59
• yes I had that in mind before, but finding the rank of a matrix of the order N*N will be extremely unfeasible. 10^20 ops in worst case, maybe more. I was looking for an alternate approach. Or if we could exploit the structure of our matrix ? I am not aware of much in that direction. Feb 8, 2014 at 19:02
• I added another hint. Feb 8, 2014 at 19:20
• if all $L_i$'s are distinct, our answer will simply be $2^M$, next case, when some of them overlap. there can be thing like $[0,2]$,$[3,5]$,$[0,5]$ rank remains $2$ not $3$. Also for $[0,6]$,$[0,3]$,$[3,6]$,$[3,3]$ rank remains $3$ not $4$. I am aware of such cases, simply not able to handle them :). Feb 8, 2014 at 19:25