Construct a binary string following the given constraints
Given three integers A, B and X. The task is to construct a binary string str which has exactly A number of 0’s and B number of 1’s provided there has to be at least X indices such that str[i] != str[i+1]. Inputs are such that there’s always a valid solution.
Examples:
Input: A = 2, B = 2, X = 1
Output: 1100
There are two 0’s and two 1’s and one (=X) index such that s[i] != s[i+1] (i.e. i = 1)Input: A = 4, B = 3, X = 2
Output: 0111000
Approach:
- Divide x by 2 and store it in a variable d.
- Check if d is even and d / 2 != a, if the condition is true then print 0 and decrement d and a by 1.
- Loop from 1 to d and print 10 and in the end update a = a – d and b = b – d.
- Finally print the remaining 0’s and 1’s depending on the values of a and b.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to print a binary string which has // 'a' number of 0's, 'b' number of 1's and there are // at least 'x' indices such that s[i] != s[i+1] int constructBinString( int a, int b, int x) { int d, i; // Divide index value by 2 and store // it into d d = x / 2; // If index value x is even and // x/2 is not equal to a if (x % 2 == 0 && x / 2 != a) { d--; cout << 0; a--; } // Loop for d for each d print 10 for (i = 0; i < d; i++) cout << "10" ; // subtract d from a and b a = a - d; b = b - d; // Loop for b to print remaining 1's for (i = 0; i < b; i++) { cout << "1" ; } // Loop for a to print remaining 0's for (i = 0; i < a; i++) { cout << "0" ; } } // Driver code int main() { int a = 4, b = 3, x = 2; constructBinString(a, b, x); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to print a binary string which has // 'a' number of 0's, 'b' number of 1's and there are // at least 'x' indices such that s[i] != s[i+1] static void constructBinString( int a, int b, int x) { int d, i; // Divide index value by 2 and store // it into d d = x / 2 ; // If index value x is even and // x/2 is not equal to a if (x % 2 == 0 && x / 2 != a) { d--; System.out.print( "0" ); a--; } // Loop for d for each d print 10 for (i = 0 ; i < d; i++) System.out.print( "10" ); // subtract d from a and b a = a - d; b = b - d; // Loop for b to print remaining 1's for (i = 0 ; i < b; i++) { System.out.print( "1" ); } // Loop for a to print remaining 0's for (i = 0 ; i < a; i++) { System.out.print( "0" ); } } // Driver code public static void main(String[] args) { int a = 4 , b = 3 , x = 2 ; constructBinString(a, b, x); } } // This code is contributed // by Mukul Singh |
Python3
# Python3 implementation of the above approach # Function to print a binary string which # has 'a' number of 0's, 'b' number of 1's # and there are at least 'x' indices such # that s[i] != s[i+1] def constructBinString(a, b, x): # Divide index value by 2 and # store it into d d = x / / 2 # If index value x is even and # x/2 is not equal to a if x % 2 = = 0 and x / / 2 ! = a: d - = 1 print ( "0" , end = "") a - = 1 # Loop for d for each d print 10 for i in range (d): print ( "10" , end = "") # subtract d from a and b a = a - d b = b - d # Loop for b to print remaining 1's for i in range (b): print ( "1" , end = "") # Loop for a to print remaining 0's for i in range (a): print ( "0" , end = "") # Driver Code if __name__ = = "__main__" : a, b, x = 4 , 3 , 2 constructBinString(a, b, x) # This code is contributed by Rituraj_Jain |
C#
// C# implementation of the approach using System; class GFG { // Function to print a binary string which has // 'a' number of 0's, 'b' number of 1's and there are // at least 'x' indices such that s[i] != s[i+1] static void constructBinString( int a, int b, int x) { int d, i; // Divide index value by 2 and store // it into d d = x / 2; // If index value x is even and // x/2 is not equal to a if (x % 2 == 0 && x / 2 != a) { d--; Console.Write( "0" ); a--; } // Loop for d for each d print 10 for (i = 0; i < d; i++) Console.Write( "10" ); // subtract d from a and b a = a - d; b = b - d; // Loop for b to print remaining 1's for (i = 0; i < b; i++) { Console.Write( "1" ); } // Loop for a to print remaining 0's for (i = 0; i < a; i++) { Console.Write( "0" ); } } // Driver code public static void Main() { int a = 4, b = 3, x = 2; constructBinString(a, b, x); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation of the // above approach // Function to print a binary string // which has 'a' number of 0's, 'b' // number of 1's and there are at least // 'x' indices such that s[i] != s[i+1] function constructBinString( $a , $b , $x ) { $d ; $i ; // Divide index value by 2 // and store it into d $d = $x / 2; // If index value x is even and // x/2 is not equal to a if ( $x % 2 == 0 && $x / 2 != $a ) { $d --; echo 0; $a --; } // Loop for d for each d print 10 for ( $i = 0; $i < $d ; $i ++) echo "10" ; // subtract d from a and b $a = $a - $d ; $b = $b - $d ; // Loop for b to print remaining 1's for ( $i = 0; $i < $b ; $i ++) { echo "1" ; } // Loop for a to print remaining 0's for ( $i = 0; $i < $a ; $i ++) { echo "0" ; } } // Driver code $a = 4; $b = 3; $x = 2; constructBinString( $a , $b , $x ); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript implementation of the approach // Function to print a binary string which has // 'a' number of 0's, 'b' number of 1's and there are // at least 'x' indices such that s[i] != s[i+1] function constructBinString(a, b, x) { let d, i; // Divide index value by 2 and store // it into d d = parseInt(x / 2, 10); // If index value x is even and // x/2 is not equal to a if (x % 2 == 0 && parseInt(x / 2, 10) != a) { d--; document.write( "0" ); a--; } // Loop for d for each d print 10 for (i = 0; i < d; i++) document.write( "10" ); // subtract d from a and b a = a - d; b = b - d; // Loop for b to print remaining 1's for (i = 0; i < b; i++) { document.write( "1" ); } // Loop for a to print remaining 0's for (i = 0; i < a; i++) { document.write( "0" ); } } let a = 4, b = 3, x = 2; constructBinString(a, b, x); </script> |
Output
0111000
Complexity Analysis:
- Time Complexity: O(max(a,b,x))
- Auxiliary Space: O(1)
Contact Us