Given a number n, find the number of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.

Video coming soon!

Subscribe for more updates

Algorithm/Insights

Binomial Coefficient: Number of ways in which k elements can be selected from n elements. This is denoted as C(n, k) and is given by- C(n, k) = n!/((n-k)!*k!)

Number of binary sequences of length n, having no 1s = 1 = (having all 0 bits)

Number of binary sequences of length n, having one 1 = Number of ways in which we can set 1 bit in n bits = C(n, 1) = n!/((n-1)!*1!) = n

Number of binary sequences of length n, having two 1s = C(n, 2) = n!/((n-2)!*2!) = n*(n-1)/2

Hence to generalize, Number of binary sequences of length n, having k 1s = C(n, k) = n!/((n-k)!*k!)

Number of sequences of length 2n having k 1s in both first half and second half: = Number of sequences of length n having k 1s * Number of sequences of length n having k 1s = C(n, k) * C(n, k)

Therefore, number of sequences of size 2n having same number 1's (and hence same sum of bits) in both first half and second half: = Sum of number of sequences of length 2n having k 1s in both first half and second half for all k = 0 to n = 1 + Σ C(n, k) * C(n, k) for k = 1 to n

Like IDeserve?

Support us by whitelisting IDeserve in your ad-blocker.

Thanks, -Team IDeserve

Algorithm Visualization

Code Snippet

package com.ideserve.questions.saurabh;
/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* Find number of binary sequences</b><br>
* Given a number n, find the number of all binary sequences of length 2n
* such that sum of first n bits is same as sum of last n bits.
* Example:
* For n = 3 Output: 20
*
* @author Saurabh
*/
public class CountBinarySequences {
public static int countBinarySequences(int n) {
if(n <= 0) {
return 0;
}
int noOfBinarySequences = 1;
int binomialCoefficient = 1;
for(int i = 1; i <= n; i++) {
binomialCoefficient = binomialCoefficient * (n-i+1)/i;
noOfBinarySequences += binomialCoefficient*binomialCoefficient;
}
return noOfBinarySequences;
}
public static void main(String[] args) {
for(int i = 0; i < 11; i++)
System.out.println("No of binary sequences for n = " + i + " = " + countBinarySequences(i));
}
}

Order of the Algorithm

Time Complexity is O(n) Space Complexity is O(1)

Contribution

Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

Saurabh Kumar

Ninja Programmer

Like IDeserve?

Support us by whitelisting IDeserve in your ad-blocker.