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

The problem “Count even length binary sequences with same sum of first and second half bits” states that you are given an integer. Now find out the number of ways to construct a binary sequence of size 2*n such that the first half and second half have the same number of set bits.

Table of Contents

Example

Explanation

The binary sequences are 0000, 1001, 1010, 0110, 0101, 1111. Thus the total count is 1.

Approach

Naive Approach

One way to solve the problem is to use recursion. So, we will keep track of the number of bits that need to be set in both halves. Thus the solution is a 3 state solution. The states are the number of bits which need to be set in first half, number of bits left to be set in second half, the number of bits traversed. A general recursive solution would look like as shown in the code below.

#include <bits/stdc++.h>
using namespace std;

int n;
int rec(int a, int b, int i){
    if(i == n)
        if(a == 0 && b == 0)
            return 1;
        else
            return 0;
    return rec(a-1, b-1, i+1) + rec(a-1, b, i+1) + rec(a, b-1, i+1) + rec(a, b, i+1);
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans += rec(i, i, 0);
        cout<<ans;
    }
}

The solution is fine but is highly inefficient. Thus to improve the time complexity. We can use Dynamic Programming. But still the time complexity will be O(N^3) because of the three states.

A Better Approach

A better approach will be to think of changing the recursive formula and use dynamic programming to solve the problem. Instead of keeping the count for the number of bits to set in the first and second half. We can reduce both the states to a single state using the difference. Now our recursive formula is changed and so our time complexity and space complexity. We can write a solution that can run in O(N^2) time.

C++ code to Count even length binary sequences with same sum of first and second half bits

#include <bits/stdc++.h>
using namespace std;

int n;
int rec(int diff, int i, vector<vector<int>> &dp){
    if(i == n)
        if(diff == 0)
            return 1;
        else
            return 0;
    if(dp[diff+n][i] != -1)
        return dp[diff+n][i];
    return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}

int main(){
    cin>>n;
    vector<vector<int>> dp(2*n+2, vector<int>(n+1, -1));
    int ans = rec(0, 0, dp);
    cout<<ans;
}

Java code to Count even length binary sequences with same sum of first and second half bits

import java.util.*;

class Main{
  static int n;
  static int rec(int diff, int i, int dp[][]){
      if(i == n)
          if(diff == 0)
              return 1;
          else
              return 0;
      if(dp[diff+n][i] != -1)
          return dp[diff+n][i];
      return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      int dp[][] = new int[2*n+2][n+1];
      for(int i=0;i<2*n+2;i++){
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = -1;
      }
      int ans = rec(0, 0, dp);
      System.out.print(ans);
  }
}

Complexity Analysis

Time Complexity

O(N^2), because there were N^2 different states in the problem. Thus the time complexity is polynomial.

Space Complexity

O(N^2), because we have created a 2D DP array. Thus the space complexity is also polynomial.

Best Approach

The Best approach is to use Binomial Coefficients to compute the answer for the problem. We can consider the two halves to be independent. Then if they are independent and we simply have to set some bits. Consider we need to set k bits out of n bits. So we can simply write the number of ways to do that is equal to nCk*nCk. Thus if we compute this value for k equal to 0 to k equal to n. We would have found the answer.

C++ code to Count even length binary sequences with same sum of first and second half bits

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int C = 1, answer = 1;
    for (int i = 1; i<=n ; i++)
    {
        C = (C * (n+1-i))/i;
        answer += (C*C);
    }
    cout<<answer;
}

Java code to Count even length binary sequences with same sum of first and second half bits

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int answer = 1, C = 1;
      for(int i = 1; i<=n; i++)
      {
          C = (C * (n+1-i))/i;
          answer += (C*C);
      }
      System.out.print(answer);
  }
}

Complexity Analysis

Time Complexity

O(N), because we have run a single loop until N. Thus the algorithm has linear time complexity.

Space Complexity

O(1), because the space complexity is constant.