Number of different binary string with k flips

Question

I am trying a problem where we are given binary string of length N(<10^5), and we are allowed exactly X(<10^5) flips on it, we are asked how many different string is possible? I am not getting idea about this, i though that it might be solved using dp, but not able to come with a recursion. Plz Help?

Example: consider the binary string of N = 3 , 1 1 1 , and X = 2 New Binary strings that can be formed after applying 2 flips are 1 1 1 (flipped the first/second/third bit twice) 0 0 1 (flipped first and second bit) 1 0 0 (flipped 2nd and 3rd bit) 0 1 0 (flipped 1st and 3rd bit)

Answer 1

Finding X-flipped strings

Consider e.g. the case where N=10, X=4 and the initial string is:

initial: 0011010111  

then this would be an example of an X-flipped string:

flipped: 0000111111  

because 4 bits are different. If you XOR the two strings, you get:

initial: 0011010111  
flipped: 0000111111  
XOR-ed:  0011101000  

where the 4 set bits (ones) in the XOR-ed string indicate the location of the 4 bits which have been flipped.

Now think of this backwards. If you have an initial string, and a string with 4 set bits, then you can generate an X-flipped string by XOR-ing them:

initial: 0011010111  
4 bits : 0011101000  
XOR-ed:  0000111111  

So if you generate every binary string of length N with X set bits, and you XOR these with the inital string, you get all the X-flipped strings.

initial     4 bits      XOR-ed  
0011010111  0000001111  0011011000
            0000010111  0011000000
            0000100111  0011110000
            ...
            1110010000  1101000111
            1110100000  1101110111
            1111000000  1100010111

Generating all N-length strings with X set bits can be done e.g. with Gosper's Hack. In the code example below I use a reverse-lexicographical order function, which I originally wrote for this answer.

Double-flipping

If bits can be flipped twice, it is possible that the X-flipped string doesn't have X bits different from the initial string, but only X-2, because one bit was flipped and then flipped back to its original state. Or X-4, if the bit was flipped 4 times, or two different bits were flipped twice. In fact, the number of different bits could be X, X-2, X-4, X-6 ... down to 1 or 0 (depending on whether X is odd or even).

So, to generate all X-flipped strings, you generate all strings with X flipped bits, then all strings with X-2 flipped bits, then X-4, X-6 ... down to 1 or 0.

If X > N

If X is greater than N, then obviously some bits will be flipped more than once. The method to generate them is the same: you start at X, count down to X-2, X-4, X-6 ... but only generate strings for values ≤ N. So practically, you start at N or N-1, depending on whether X-N is even or odd.

Total number of strings

The number of N-length strings with X flipped bits equals the number of N-length strings with X set bits, which is the Binomial Coefficient N choose X. Of course you have to take into account the strings with X-2, X-4, X-6 ... flipped bits too, so the total is:

(N choose X) + (N choose X-2) + (N choose X-4) + (N choose X-6) + ... + (N choose (1 or 0))

In the case where X is greater than N, you start at N choose N or N choose N-1, depending on whether X-N is even or odd.

For your example with N=3 and X=2, the total number is:

(3 choose 2) + (3 choose 0) = 3 + 1 = 4  

For the example above with N=10 and X=4, the total number is:

(10 choose 4) + (10 choose 2) + (10 choose 0) = 210 + 45 + 1 = 256  

For the example in the other answer with N=6 and X=4, the correct number is:

(6 choose 4) + (6 choose 2) + (6 choose 0) = 15 + 15 + 1 = 31  

Example code

This JavaScript code snippet generates the sequences of binary strings in reverse lexicographical order (so that the set bits move from left to right) and then prints out the resulting flipped strings and the total count for the examples described above:

function flipBits(init, x) {
    var n = init.length, bits = [], count = 0;
    if (x > n) x = n - (x - n) % 2;   // reduce x if it is greater than n
    for (; x >= 0; x -= 2) {          // x, x-2, x-4, ... down to 1 or 0
        for (var i = 0; i < n; i++) bits[i] = i < x ? 1 : 0;    // x ones, then zeros
        do {++count;
            var flip = XOR(init, bits);
            document.write(init + " &oplus; " + bits + " &rarr; " + flip + "<br>");
        } while (revLexi(bits));
    }
    return count;
    function XOR(a, b) {              // XOR's two binary arrays (because JavaScript)
        var c = [];
        for (var i = 0; i < a.length; i++) c[i] = a[i] ^ b[i];
        return c;
    }
    function revLexi(seq) {           // next string in reverse lexicographical order
        var max = true, pos = seq.length, set = 1;
        while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
        if (pos < 0) return false;
        seq[pos] = 0;
        while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
        return true;
    }
}
document.write(flipBits([1,1,1], 2) + "<br>");
document.write(flipBits([0,0,1,1,0,1,0,1,1,1], 4) + "<br>");
document.write(flipBits([1,1,1,1,1,1], 4) + "<br>");