Count even length binary sequences with same sum of first and second half bits - GeeksforGeeks

Count even length binary sequences with same sum of first and second half bits - GeeksforGeeks
Given a number n, find count of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.

Input:  n = 1
Output: 2
There are 2 sequences of length 2*n, the
sequences are 00 and 11

Input:  n = 2
Output: 2
There are 6 sequences of length 2*n, the
sequences are 0101, 0110, 1010, 1001, 0000
and 1111

The idea is to fix first and last bits and then recur for n-1, i.e., remaining 2(n-1) bits. There are following possibilities when we fix first and last bits.
1) First and last bits are same, remaining n-1 bits on both sides should also have the same sum.
2) First bit is 1 and last bit is 0, sum of remaining n-1 bits on left side should be 1 less than the sum n-1 bits on right side.
2) First bit is 0 and last bit is 1, sum of remaining n-1 bits on left side should be 1 more than the sum n-1 bits on right side

diff is the expected difference between sum of first half digits and last half digits. Initially diff is 0.

                  // When first and last bits are same
                  // there are two cases, 00 and 11
count(n, diff) =  2*count(n-1, diff) +    
    
                 // When first bit is 1 and last bit is 0
                 count(n-1, diff-1) +

                 // When first bit is 0 and last bit is 1
                 count(n-1, diff+1)

What should be base cases?
// When n == 1 (2 bit sequences)
1) If n == 1 and diff == 0, return 2
2) If n == 1 and |diff| == 1, return 1 

// We can't cover difference of more than n with 2n bits
3) If |diff| > n, return 0

// diff is difference between sums 

// first n bits and last n bits respectively

static int countSeq(int n, int diff)

{

    // We can't cover difference of more

    // than n with 2n bits

    if (Math.abs(diff) > n)

        return 0;

  

    // n == 1, i.e., 2 bit long sequences

    if (n == 1 && diff == 0)

        return 2;

    if (n == 1 && Math.abs(diff) == 1)

        return 1;

  

    int res = // First bit is 0 & last bit is 1

            countSeq(n-1, diff+1) +

  

            // First and last bits are same

            2*countSeq(n-1, diff) +

  

            // First bit is 1 & last bit is 0

            countSeq(n-1, diff-1);

  

    return res;

}

DP-O(N^2) - a memoization based solution that uses a lookup table to compute the result.

// dif is diference between sums of first 

// n bits and last n bits i.e., 

// dif = (Sum of first n bits) - (Sum of last n bits)

static int countSeqUtil(int n, int dif)

{

    // We can't cover diference of

    // more than n with 2n bits

    if (Math.abs(dif) > n)

        return 0;

  

    // n == 1, i.e., 2 bit long sequences

    if (n == 1 && dif == 0)

        return 2;

    if (n == 1 && Math.abs(dif) == 1)

        return 1;

  

    // Check if this subbproblem is already

    // solved n is added to dif to make 

    // sure index becomes positive

    if (lookup[n][n+dif] != -1)

        return lookup[n][n+dif];

  

    int res = // First bit is 0 & last bit is 1

            countSeqUtil(n-1, dif+1) +

  

            // First and last bits are same

            2*countSeqUtil(n-1, dif) +

  

            // First bit is 1 & last bit is 0

            countSeqUtil(n-1, dif-1);

  

    // Store result in lookup table 

    // and return the result

    return lookup[n][n+dif] = res;

}

  

// A Wrapper over countSeqUtil(). It mainly 

// initializes lookup table, then calls 

// countSeqUtil()

static int countSeq(int n)

{

    // Initialize all entries of lookup

    // table as not filled 

    // memset(lookup, -1, sizeof(lookup));

    for(int k = 0; k < lookup.length; k++)

    {

        for(int j = 0; j < lookup.length; j++)

        {

        lookup[k][j] = -1;

    }

    } 

      

    // call countSeqUtil()

    return countSeqUtil(n, 0);

}

O(n)

No. of 2*n bit strings such that first n bits have 0 ones & 
last n bits have 0 ones = nC0 * nC0

No. of 2*n bit strings such that first n bits have 1 ones & 
last n bits have 1 ones = nC1 * nC1

....

and so on.

Result = nC0*nC0 + nC1*nC1 + ... + nCn*nCn
       = ∑(nCk)2 
        0 <= k <= n 

// Returns the count of even length sequences

int countSeq(int n)

{

    int nCr=1, res = 1;

    // Calculate SUM ((nCr)^2)

    for (int r = 1; r<=n ; r++)

    {

        // Compute nCr using nC(r-1)

        // nCr/nC(r-1) = (n+1-r)/r;

        nCr = (nCr * (n+1-r))/r;  

        res += nCr*nCr;

    }

    return res;

}

Recursive:

// diff is difference between sums first n bits

// and last n bits respectively

int countSeq(int n, int diff)

{

    // We can't cover difference of more

    // than n with 2n bits

    if (abs(diff) > n)

        return 0;

    // n == 1, i.e., 2 bit long sequences

    if (n == 1 && diff == 0)

        return 2;

    if (n == 1 && abs(diff) == 1)

        return 1;

    int res = // First bit is 0 & last bit is 1

              countSeq(n-1, diff+1) +

              // First and last bits are same

              2*countSeq(n-1, diff) +

              // First bit is 1 & last bit is 0

              countSeq(n-1, diff-1);

    return res;

}

http://www.geeksforgeeks.org/find-all-even-length-binary-sequences-with-same-sum-of-first-and-second-half-bits/
Given a number n, find all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.

The idea is to fix first and last bits and then recur for remaining 2*(n-1) bits. There are four possibilities when we fix first and last bits –

1. First and last bits are 1, remaining n – 1 bits on both sides should also have the same sum.
2. First and last bits are 0, remaining n – 1 bits on both sides should also have the same sum.
3. First bit is 1 and last bit is 0, sum of remaining n – 1 bits on left side should be 1 less than the sum n-1 bits on right side.
4. First bit is 0 and last bit is 1, sum of remaining n – 1 bits on left side should be 1 more than the sum n-1 bits on right side.

void findAllSequences(int diff, char* out, int start, int end)

{

    // We can't cover difference of more than n with 2n bits

    if (abs(diff) > (end - start + 1) / 2)

        return;

    // if all bits are filled

    if (start > end)

    {

        // if sum of first n bits and last n bits are same

        if (diff == 0)

            cout << out << " ";

        return;

    }

    // fill first bit as 0 and last bit as 1

    out[start] = '0', out[end] = '1';

    findAllSequences(diff + 1, out, start + 1, end - 1);

    // fill first and last bits as 1

    out[start] = out[end] = '1';

    findAllSequences(diff, out, start + 1, end - 1);

    // fill first and last bits as 0

    out[start] = out[end] = '0';

    findAllSequences(diff, out, start + 1, end - 1);

    // fill first bit as 1 and last bit as 0

    out[start] = '1', out[end] = '0';

    findAllSequences(diff - 1, out, start + 1, end - 1);

}




Read full article from Count even length binary sequences with same sum of first and second half bits - GeeksforGeeks