Given a number N, find all binary sequences of length 2*N such that sum of first N bits is same as the sum of last N bits.
Examples:
Input: N = 2
Output:
0000
0101
0110
1001
1010
1111Input: N = 1
Output:
00
11
Note: The recursive approach to this problem can be found here.
Approach:
A simple approach to run a loop from 0 to 22*N and convert into the binary form and check whether the sum of first half is equal to the sum of the second half.
If the above condition is true, then print that number, else check for the next one.
Below is the implementation of the above approach:
C++
// C++ implementation#include <iostream>#include <malloc.h>#include <math.h>using namespace std;// Function to convert the// number into binary and// store the number into// an arrayvoid convertToBinary(int num, int a[], int n){ int pointer = n - 1; while (num > 0) { a[pointer] = num % 2; num = num / 2; pointer--; }}// Function to check if the// sum of the digits till// the mid of the array and// the sum of the digits// from mid till n is the// same, if they are same// then print that binaryvoid checkforsum(int a[], int n){ int sum1 = 0; int sum2 = 0; int mid = n / 2; // Calculating the sum from // 0 till mid and store // in sum1 for (int i = 0; i < mid; i++) sum1 = sum1 + a[i]; // Calculating the sum // from mid till n and // store in sum2 for (int j = mid; j < n; j++) sum2 = sum2 + a[j]; // If sum1 is same as // sum2 print the binary if (sum1 == sum2) { for (int i = 0; i < n; i++) cout << a[i]; cout << "\n"; }}// Function to print sequencevoid print_seq(int m){ int n = (2 * m); // Creating the array int a[n]; // Initialize the array // with 0 to store the // binary nnumbers for (int j = 0; j < n; j++) { a[j] = 0; } for (int i = 0; i < (int)pow(2, n); i++) { // Converting the number // into binary first convertToBinary(i, a, n); // Checking if the sum of // the first half of the // array is same as the // sum of the next half checkforsum(a, n); }}// Driver Codeint main(){ int m = 2; print_seq(m); return 0;} |
Java
// Java code implementation for above approachclass GFG{ // Function to convert the // number into binary and // store the number into // an array static void convertToBinary(int num, int a[], int n) { int pointer = n - 1; while (num > 0) { a[pointer] = num % 2; num = num / 2; pointer--; } } // Function to check if the // sum of the digits till // the mid of the array and // the sum of the digits // from mid till n is the // same, if they are same // then print that binary static void checkforsum(int a[], int n) { int sum1 = 0; int sum2 = 0; int mid = n / 2; // Calculating the sum from // 0 till mid and store // in sum1 for (int i = 0; i < mid; i++) sum1 = sum1 + a[i]; // Calculating the sum // from mid till n and // store in sum2 for (int j = mid; j < n; j++) sum2 = sum2 + a[j]; // If sum1 is same as // sum2 print the binary if (sum1 == sum2) { for (int i = 0; i < n; i++) System.out.print(a[i]); System.out.println(); } } // Function to print sequence static void print_seq(int m) { int n = (2 * m); // Creating the array int a[] = new int[n]; // Initialize the array // with 0 to store the // binary nnumbers for (int j = 0; j < n; j++) { a[j] = 0; } for (int i = 0; i < (int)Math.pow(2, n); i++) { // Converting the number // into binary first convertToBinary(i, a, n); // Checking if the sum of // the first half of the // array is same as the // sum of the next half checkforsum(a, n); } } // Driver Code public static void main (String[] args) { int m = 2; print_seq(m); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of above approach# Function to convert the number into binary # and store the number into an arraydef convertToBinary(num, a, n): pointer = n - 1 while (num > 0): a[pointer] = num % 2 num = num // 2 pointer -= 1# Function to check if the sum of the digits till# the mid of the array and the sum of the digits# from mid till n is the same, if they are same# then print that binarydef checkforsum(a, n): sum1 = 0 sum2 = 0 mid = n // 2 # Calculating the sum from 0 till mid # and store in sum1 for i in range(mid): sum1 = sum1 + a[i] # Calculating the sum from mid till n # and store in sum2 for j in range(mid, n): sum2 = sum2 + a[j] # If sum1 is same as sum2 print the binary if (sum1 == sum2): for i in range(n): print(a[i], end = "") print()# Function to print sequencedef print_seq(m): n = (2 * m) # Creating the array a = [0 for i in range(n)] for i in range(pow(2, n)): # Converting the number # into binary first convertToBinary(i, a, n) # Checking if the sum of the first half # of the array is same as the sum of # the next half checkforsum(a, n)# Driver Codem = 2print_seq(m)# This code is contributed by mohit kumar |
C#
// C# code implementation for above approachusing System; class GFG{ // Function to convert the // number into binary and // store the number into // an array static void convertToBinary(int num, int []a, int n) { int pointer = n - 1; while (num > 0) { a[pointer] = num % 2; num = num / 2; pointer--; } } // Function to check if the // sum of the digits till // the mid of the array and // the sum of the digits // from mid till n is the // same, if they are same // then print that binary static void checkforsum(int []a, int n) { int sum1 = 0; int sum2 = 0; int mid = n / 2; // Calculating the sum from // 0 till mid and store // in sum1 for (int i = 0; i < mid; i++) sum1 = sum1 + a[i]; // Calculating the sum // from mid till n and // store in sum2 for (int j = mid; j < n; j++) sum2 = sum2 + a[j]; // If sum1 is same as // sum2 print the binary if (sum1 == sum2) { for (int i = 0; i < n; i++) Console.Write(a[i]); Console.WriteLine(); } } // Function to print sequence static void print_seq(int m) { int n = (2 * m); // Creating the array int []a = new int[n]; // Initialize the array // with 0 to store the // binary nnumbers for (int j = 0; j < n; j++) { a[j] = 0; } for (int i = 0; i < (int)Math.Pow(2, n); i++) { // Converting the number // into binary first convertToBinary(i, a, n); // Checking if the sum of // the first half of the // array is same as the // sum of the next half checkforsum(a, n); } } // Driver Code public static void Main (String[] args) { int m = 2; print_seq(m); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation// Function to convert the// number into binary and// store the number into// an arrayfunction convertToBinary(num, a, n){ let pointer = n - 1; while (num > 0) { a[pointer] = num % 2; num = parseInt(num / 2); pointer--; }}// Function to check if the// sum of the digits till// the mid of the array and// the sum of the digits// from mid till n is the// same, if they are same// then print that binaryfunction checkforsum(a, n){ let sum1 = 0; let sum2 = 0; let mid = parseInt(n / 2); // Calculating the sum from // 0 till mid and store // in sum1 for (let i = 0; i < mid; i++) sum1 = sum1 + a[i]; // Calculating the sum // from mid till n and // store in sum2 for (let j = mid; j < n; j++) sum2 = sum2 + a[j]; // If sum1 is same as // sum2 print the binary if (sum1 == sum2) { for (let i = 0; i < n; i++) document.write(a[i]); document.write("<br>"); }}// Function to print sequencefunction print_seq(m){ let n = (2 * m); // Creating the array let a = new Array(n); // Initialize the array // with 0 to store the // binary nnumbers for (let j = 0; j < n; j++) { a[j] = 0; } for (let i = 0; i < Math.pow(2, n); i++) { // Converting the number // into binary first convertToBinary(i, a, n); // Checking if the sum of // the first half of the // array is same as the // sum of the next half checkforsum(a, n); }}// Driver Code let m = 2; print_seq(m);</script> |
Output:
0000 0101 0110 1001 1010 1111
Time Complexity: O(N*22N)
Auxiliary Space: O(N)
