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.
Examples:
Input: n = 1 Output: 2 There are 2 sequences of length 2*n, the sequences are 00 and 11 Input: n = 2 Output: 6 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.
Based on above facts, we get below recurrence formula.
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
Below is the implementation based of above Naive Recursive Solution.
C++
// A Naive Recursive C++ program to count even// length binary sequences such that the sum of// first and second half bits is same#include<bits/stdc++.h>using namespace std;// diff is difference between sums first n bits// and last n bits respectivelyint 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;}// Driver programint main(){ int n = 2; cout << "Count of sequences is " << countSeq(2, 0); return 0;} |
Java
// A Naive Recursive Java program to // count even length binary sequences // such that the sum of first and // second half bits is sameimport java.io.*;class GFG {// diff is difference between sums // first n bits and last n bits respectivelystatic 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;}// Driver programpublic static void main(String[] args){ int n = 2; System.out.println("Count of sequences is " + countSeq(2, 0));}}// This code is contributed by Prerna Saini |
Python3
# A Naive Recursive Python # program to count even length # binary sequences such that # the sum of first and second # half bits is same# diff is difference between # sums first n bits and last # n bits respectivelydef countSeq(n, 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 and diff == 0): return 2 if (n == 1 and abs(diff) == 1): return 1 # First bit is 0 & last bit is 1 # First and last bits are same # First bit is 1 & last bit is 0 res = (countSeq(n - 1, diff + 1) + 2 * countSeq(n - 1, diff) + countSeq(n - 1, diff - 1)) return res# Driver Coden = 2;print("Count of sequences is %d " % (countSeq(2, 0))) # This code is contributed # by Shivi_Aggarwal |
C#
// A Naive Recursive C# program to // count even length binary sequences // such that the sum of first and // second half bits is sameusing System;class GFG { // 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; // 1. First bit is 0 & last bit is 1 // 2. First and last bits are same // 3. First bit is 1 & last bit is 0 int res = countSeq(n-1, diff+1) + 2 * countSeq(n-1, diff) + countSeq(n-1, diff-1); return res; } // Driver program public static void Main() { Console.Write("Count of sequences is " + countSeq(2, 0)); }}// This code is contributed by nitin mittal. |
PHP
<?php// A Naive Recursive PHP program // to count even length binary // sequences such that the sum of// first and second half bits is same// diff is difference between // sums first n bits and last// n bits respectivelyfunction countSeq($n, $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; $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;}// Driver Code$n = 2;echo "Count of sequences is ", countSeq($n, 0);// This code is contributed// by shiv_bhakt.?> |
Javascript
<script>// A Naive Recursive Javascript program to // count even length binary sequences // such that the sum of first and // second half bits is same // diff is difference between sums // first n bits and last n bits respectively function countSeq(n,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; let 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; } // Driver program let n = 2; document.write("Count of sequences is " + countSeq(2, 0)); // This code is contributed by avanitrachhadiya2155</script> |
Output
Count of sequences is 6
The time complexity of above solution is exponential. If we draw the complete recursion tree, we can observer that many subproblems are solved again and again. For example, when we start from n = 4 and diff = 0, we can reach (3, 0) through multiple paths. Since same subproblems are called again, this problem has Overlapping subproblems property. So min square sum problem has both properties (see this and this) of a Dynamic Programming problem.
Below is a memoization based solution that uses a lookup table to compute the result.
C++
// A memoization based C++ program to count even// length binary sequences such that the sum of// first and second half bits is same#include<bits/stdc++.h>using namespace std;#define MAX 1000// A lookup table to store the results of subproblemsint lookup[MAX][MAX];// dif is difference between sums of first n bits// and last n bits i.e., dif = (Sum of first n bits) -// (Sum of last n bits)int countSeqUtil(int n, int dif){ // We can't cover difference of more // than n with 2n bits if (abs(dif) > n) return 0; // n == 1, i.e., 2 bit long sequences if (n == 1 && dif == 0) return 2; if (n == 1 && abs(dif) == 1) return 1; // Check if this subproblem 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()int countSeq(int n){ // Initialize all entries of lookup table as not filled memset(lookup, -1, sizeof(lookup)); // call countSeqUtil() return countSeqUtil(n, 0);}// Driver programint main(){ int n = 2; cout << "Count of sequences is " << countSeq(2); return 0;} |
Java
// A memoization based Java program to // count even length binary sequences // such that the sum of first and // second half bits is sameimport java.io.*;class GFG { // A lookup table to store the results of // subproblemsstatic int lookup[][] = new int[1000][1000];// dif is difference 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 difference 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 subproblem 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);}// Driver programpublic static void main(String[] args){ int n = 2; System.out.println("Count of sequences is " + countSeq(2));}}// This code is contributed by Prerna Saini |
Python3
#A memoization based python program to count even#length binary sequences such that the sum of #first and second half bits is same MAX=1000#A lookup table to store the results of subproblemslookup=[[0 for i in range(MAX)] for i in range(MAX)]#dif is difference between sums of first n bits#and last n bits i.e., dif = (Sum of first n bits) -# (Sum of last n bits) def countSeqUtil(n,dif): #We can't cover difference of more #than n with 2n bits if abs(dif)>n: return 0 #n == 1, i.e., 2 bit long sequences if n==1 and dif==0: return 2 if n==1 and abs(dif)==1: return 1 #Check if this subproblem 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] #First bit is 0 & last bit is 1 #+First and last bits are same #+First bit is 1 & last bit is 0 res= (countSeqUtil(n-1, dif+1)+ 2*countSeqUtil(n-1, dif)+ countSeqUtil(n-1, dif-1)) #Store result in lookup table and return the result lookup[n][n+dif]=res return res#A Wrapper over countSeqUtil(). It mainly initializes lookup #table, then calls countSeqUtil() def countSeq(n): #Initialize all entries of lookup table as not filled global lookup lookup=[[-1 for i in range(MAX)] for i in range(MAX)] #call countSeqUtil() res=countSeqUtil(n,0) return res#Driver Codeif __name__=='__main__': n=2 print('Count of Sequences is ',countSeq(n)) #This Code is contributed by sahilshelangia |
C#
// A memoization based C# program to // count even length binary sequences // such that the sum of first and // second half bits is same using System;class GFG { // A lookup table to store the results of // subproblems static int [,]lookup = new int[1000,1000]; // dif is difference 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 difference 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 subproblem 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.GetLength(0); k++) { for(int j = 0; j < lookup.GetLength(1); j++) { lookup[k,j] = -1; } } // call countSeqUtil() return countSeqUtil(n, 0); } // Driver program public static void Main() { int n = 2; Console.WriteLine("Count of sequences is " + countSeq(n)); } } // This code is contributed by Ryuga |
PHP
<?php// A memoization based PHP program to count even// length binary sequences such that the sum of// first and second half bits is same$MAX = 1000;// A lookup table to store the results // of subproblems$lookup = array_fill(0, $MAX, array_fill(0, $MAX, -1));// dif is difference between sums of first n bits// and last n bits i.e., dif = (Sum of first n bits) -// (Sum of last n bits)function countSeqUtil($n, $dif){ global $lookup; // We can't cover difference of more // than n with 2n bits if (abs($dif) > $n) return 0; // n == 1, i.e., 2 bit long sequences if ($n == 1 && $dif == 0) return 2; if ($n == 1 && abs($dif) == 1) return 1; // Check if this subproblem 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]; $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()function countSeq($n){ // Initialize all entries of // lookup table as not filled // call countSeqUtil() return countSeqUtil($n, 0);}// Driver Code$n = 2;echo "Count of sequences is " . countSeq($n);// This code is contributed by mits?> |
Javascript
<script>// A memoization based Javascript program to// count even length binary sequences// such that the sum of first and// second half bits is same // A lookup table to store the results of // subproblems let lookup = new Array(1000); for(let i = 0; i < 1000; i++) { lookup[i] = new Array(1000); } // dif is difference between sums of first // n bits and last n bits i.e., // dif = (Sum of first n bits) - (Sum of last n bits) function countSeqUtil(n, dif) { // We can't cover difference 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 subproblem 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]; let 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() function countSeq(n) { // Initialize all entries of lookup // table as not filled // memset(lookup, -1, sizeof(lookup)); for(let k = 0; k < lookup.length; k++) { for(let j = 0; j < lookup.length; j++) { lookup[k][j] = -1; } } // call countSeqUtil() return countSeqUtil(n, 0); } // Driver program let n = 2; document.write("Count of sequences is " + countSeq(2)); // This code is contributed by rag2127</script> |
Output
Count of sequences is 6
Worst case time complexity of this solution is O(n2) as diff can be maximum n.
Below is O(n) solution for the same.
Number of n-bit strings with 0 ones = nC0 Number of n-bit strings with 1 ones = nC1 ... Number of n-bit strings with k ones = nCk ... Number of n-bit strings with n ones = nCn
So, we can get required result using below
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
Below is the implementation based on above idea.
C++
// A O(n) C++ program to count even length binary sequences// such that the sum of first and second half bits is same#include<iostream>using namespace std;// Returns the count of even length sequencesint 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;}// Driver programint main(){ int n = 2; cout << "Count of sequences is " << countSeq(n); return 0;} |
Java
// Java program to find remaining// chocolates after k iterationsimport java.io.*;class GFG { // A O(n) C++ program to count // even length binary sequences // such that the sum of first // and second half bits is same // Returns the count of // even length sequences static 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; } // Driver code public static void main(String args[]) { int n = 2; System.out.print("Count of sequences is "); System.out.println(countSeq(n)); }}// This code is contributed// by Shivi_Aggarwal |
Python
# A Python program to count # even length binary sequences # such that the sum of first # and second half bits is same # Returns the count of # even length sequences def countSeq(n): nCr = 1 res = 1 # Calculate SUM ((nCr)^2) for r in range(1, n + 1): # 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; # Driver Coden = 2print("Count of sequences is"),print (int(countSeq(n))) # This code is contributed# by Shivi_Aggarwal |
C#
// C# program to find remaining// chocolates after k iterationusing System;class GFG { // A O(n) C# program to count// even length binary sequences// such that the sum of first// and second half bits is same// Returns the count of // even length sequencesstatic 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;}// Driver codepublic static void Main(){ int n = 2; Console.Write("Count of sequences is "); Console.Write(countSeq(n));}}// This code is contributed // by ChitraNayal |
PHP
<?php// A Php program to count even // length binary sequences // such that the sum of first// and second half bits is same // Returns the count of// even length sequences function countSeq($n) { $nCr = 1; $res = 1; // Calculate SUM ((nCr)^2) for ($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 = $res + ($nCr * $nCr); } return $res; } // Driver Code $n = 2; echo ("Count of sequences is ");echo countSeq($n); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript program to find remaining chocolates after k iteration // A O(n) C# program to count // even length binary sequences // such that the sum of first // and second half bits is same // Returns the count of // even length sequences function countSeq(n) { let nCr = 1, res = 1; // Calculate SUM ((nCr)^2) for (let 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; } let n = 2; document.write("Count of sequences is "); document.write(countSeq(n)); // This code is contributed by mukesh07.</script> |
Output
Count of sequences is 6
Thanks to d_neveropen, Saurabh Jain and Mysterious Mind for suggesting above O(n) solution.
This article is contributed by Pawan. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
