K-th Lexicographically smallest binary string with A 0s and B 1s

0 0 7 minutes read

Given three positive integers A, B, and K, the task is to find the K^th 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 K^th 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>

Output:

Time Complexity: O(A*B)
Auxiliary Space: O(A*B)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!