Given three positive integers A, B, and K, the task is to find the Kth lexicographically smallest binary string that contains exactly A number of 0s and B number of 1s.
Example:
Input: A = 2, B = 2, K = 4
Output: 1001
Explanation: The lexicographic order of the strings is 0011, 0101, 0110, 1001.Input: A = 3, B = 3, K = 7
Output: 010110
Approach: The above problem can be solved by using Dynamic Programming. Follow the below steps to solve this problem:
- Initialize a 2D array dp[][] such that dp[i][j] will denote the total number of binary strings with i number of 0s and j number of 1s.
- All the dp table values are initially filled with zeroes except dp[0][0] = 1 which denotes an empty string.
- Now, dp[i][j] can be calculated as the sum of the total number of strings ending with 0(using the dp state as dp[i – 1][j]) and the string ending with 1(using the dp state as dp[i][j – 1]). So, the current dp state is calculated as dp[i][j] = dp[i – 1][j] + dp[i][j – 1].
- After filling this dp table, a recursive function can be used to calculate the Kth lexicographically smallest binary string.
- So, define a function KthString having parameters A, B, K, and dp.
- Now, in each call of this recursive function:
- If the value of dp[A][B] is at least K then only ‘0’ can be present at this position in the Kth lexicographically smallest binary string and then recursively call function for the state (A – 1, B).
- Else ‘1’ is present here and recursively call function for the state (A, B – 1).
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Recursive function to find the Kth // smallest binary string string KthString( int A, int B, long long K, vector<vector< int > >& dp) { // Base Case if (A == 0) { // Return string of all 1's // of length B return string(B, '1' ); } if (B == 0) { // Return string of all 0's // of length A return string(A, '0' ); } if (K <= dp[A - 1][B]) { return "0" + KthString( A - 1, B, K, dp); } else { return "1" + KthString( A, B - 1, K - dp[A - 1][B], dp); } } // Function to find the Kth lexicographically // smallest binary string with exactly // A zeroes and B ones int KthStringUtil( int A, int B, int K) { // Stores the recurring states vector<vector< int > > dp( A + 1, vector< int >(B + 1)); // Calculate the dp values iteratively dp[0][0] = 1; for ( int i = 0; i <= A; ++i) { for ( int j = 0; j <= B; ++j) { if (i > 0) { // The last character was '0' dp[i][j] += dp[i - 1][j]; } if (j > 0) { // The last character was '1' dp[i][j] += dp[i][j - 1]; } } } // Print the binary string obtained cout << KthString(A, B, K, dp); return 0; } // Driver Code int main() { int A = 3, B = 3, K = 7; KthStringUtil(A, B, K); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Recursive function to find the Kth // smallest binary string static String KthString( int A, int B, long K, int [][] dp) { // Base Case if (A == 0 ) { // Return string of all 1's // of length B String ans = "" ; for ( int i = 0 ; i < B; i++) { ans += '1' ; } return ans; } if (B == 0 ) { // Return string of all 0's // of length A String ans = "" ; for ( int i = 0 ; i < A; i++) { ans += '0' ; } return ans; } if (K <= dp[A - 1 ][B]) { return "0" + KthString(A - 1 , B, K, dp); } else { return "1" + KthString(A, B - 1 , K - dp[A - 1 ][B], dp); } } // Function to find the Kth lexicographically // smallest binary string with exactly // A zeroes and B ones static int KthStringUtil( int A, int B, int K) { // Stores the recurring states int [][] dp = new int [A + 1 ][B + 1 ]; // Calculate the dp values iteratively dp[ 0 ][ 0 ] = 1 ; for ( int i = 0 ; i <= A; ++i) { for ( int j = 0 ; j <= B; ++j) { if (i > 0 ) { // The last character was '0' dp[i][j] += dp[i - 1 ][j]; } if (j > 0 ) { // The last character was '1' dp[i][j] += dp[i][j - 1 ]; } } } // Print the binary string obtained System.out.println(KthString(A, B, K, dp)); return 0 ; } // Driver Code public static void main(String[] args) { int A = 3 , B = 3 , K = 7 ; KthStringUtil(A, B, K); } } // This code is contributed by Dharanendra L V. |
Python3
# Python Program to implement # the above approach # Recursive function to find the Kth # smallest binary string def KthString(A, B, K, dp): # Base Case if (A = = 0 ): # Return string of all 1's # of length B str = "" for i in range (B): str + = '1' return str if (B = = 0 ): # Return string of all 0's # of length A str = "" for i in range (A): str + = '0' return str if (K < = dp[A - 1 ][B]): return "0" + KthString( A - 1 , B, K, dp) else : return "1" + KthString( A, B - 1 , K - dp[A - 1 ][B], dp) # Function to find the Kth lexicographically # smallest binary string with exactly # A zeroes and B ones def KthStringUtil(A, B, K): # Stores the recurring states dp = [ 0 ] * (A + 1 ) for i in range ( len (dp)): dp[i] = [ 0 ] * (B + 1 ) # Calculate the dp values iteratively dp[ 0 ][ 0 ] = 1 for i in range (A + 1 ): for j in range (B + 1 ): if (i > 0 ): # The last character was '0' dp[i][j] + = dp[i - 1 ][j] if (j > 0 ): # The last character was '1' dp[i][j] + = dp[i][j - 1 ] # Print the binary string obtained print (KthString(A, B, K, dp)) # Driver Code A = 3 B = 3 K = 7 KthStringUtil(A, B, K) # This code is contributed by gfgking. |
C#
// C# program for the above approach using System; class GFG { // Recursive function to find the Kth // smallest binary string static string KthString( int A, int B, long K, int [, ] dp) { // Base Case if (A == 0) { // Return string of all 1's // of length B string ans = "" ; for ( int i = 0; i < B; i++) { ans += '1' ; } return ans; } if (B == 0) { // Return string of all 0's // of length A string ans = "" ; for ( int i = 0; i < A; i++) { ans += '0' ; } return ans; } if (K <= dp[A - 1, B]) { return "0" + KthString(A - 1, B, K, dp); } else { return "1" + KthString(A, B - 1, K - dp[A - 1, B], dp); } } // Function to find the Kth lexicographically // smallest binary string with exactly // A zeroes and B ones static int KthStringUtil( int A, int B, int K) { // Stores the recurring states int [, ] dp = new int [A + 1, B + 1]; // Calculate the dp values iteratively dp[0, 0] = 1; for ( int i = 0; i <= A; ++i) { for ( int j = 0; j <= B; ++j) { if (i > 0) { // The last character was '0' dp[i, j] += dp[i - 1, j]; } if (j > 0) { // The last character was '1' dp[i, j] += dp[i, j - 1]; } } } // Print the binary string obtained Console.WriteLine(KthString(A, B, K, dp)); return 0; } // Driver Code public static void Main( string [] args) { int A = 3, B = 3, K = 7; KthStringUtil(A, B, K); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Recursive function to find the Kth // smallest binary string function KthString(A, B, K, dp) { // Base Case if (A == 0) { // Return string of all 1's // of length B let str = "" ; for (let i = 0; i < B; i++) { str += '1 '; } return str; } if (B == 0) { // Return string of all 0' s // of length A let str = "" ; for (let i = 0; i < A; i++) { str += '0' ; } return str; } if (K <= dp[A - 1][B]) { return "0" + KthString( A - 1, B, K, dp); } else { return "1" + KthString( A, B - 1, K - dp[A - 1][B], dp); } } // Function to find the Kth lexicographically // smallest binary string with exactly // A zeroes and B ones function KthStringUtil(A, B, K) { // Stores the recurring states let dp = new Array(A + 1); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(B + 1).fill(0); } // Calculate the dp values iteratively dp[0][0] = 1; for (let i = 0; i <= A; ++i) { for (let j = 0; j <= B; ++j) { if (i > 0) { // The last character was '0' dp[i][j] += dp[i - 1][j]; } if (j > 0) { // The last character was '1' dp[i][j] += dp[i][j - 1]; } } } // Print the binary string obtained document.write(KthString(A, B, K, dp)); return 0; } // Driver Code let A = 3, B = 3, K = 7; KthStringUtil(A, B, K); // This code is contributed by Potta Lokesh </script> |
010110
Time Complexity: O(A*B)
Auxiliary Space: O(A*B)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!