Dados tres números enteros positivos A , B y K , la tarea es encontrar la K ésima string binaria lexicográficamente más pequeña que contenga exactamente A un número de 0 y B un número de 1 .
Ejemplo:
Entrada: A = 2, B = 2, K = 4
Salida: 1001
Explicación: El orden lexicográfico de las strings es 0011, 0101, 0110, 1001.Entrada: A = 3, B = 3, K = 7
Salida: 010110
Enfoque: El problema anterior se puede resolver mediante el uso de Programación Dinámica . Siga los pasos a continuación para resolver este problema:
- Inicialice una array 2D dp[][] tal que dp[i][j] indicará el número total de strings binarias con i número de 0 y j número de 1 .
- Todos los valores de la tabla dp se llenan inicialmente con ceros excepto dp[0][0] = 1 que denota una string vacía.
- Ahora, dp[i][j] se puede calcular como la suma del número total de strings que terminan en 0 (usando el estado dp como dp[i – 1][j] ) y la string que termina en 1 (usando el dp estado como dp[i][j – 1] ). Entonces, el estado actual de dp se calcula como dp[i][j] = dp[i – 1][j] + dp[i][j – 1] .
- Después de llenar esta tabla dp, se puede usar una función recursiva para calcular la K -ésima string binaria lexicográficamente más pequeña.
- Entonces, defina una función KthString que tenga los parámetros A, B, K y dp .
- Ahora, en cada llamada de esta función recursiva:
- Si el valor de dp[A][B] es al menos K , entonces solo ‘0’ puede estar presente en esta posición en la K-ésima string binaria lexicográficamente más pequeña y luego llamar recursivamente a la función para el estado (A – 1, B) .
- De lo contrario, ‘1’ está presente aquí y recursivamente llama a la función para el estado (A, B – 1) .
- Escriba la respuesta de acuerdo con la observación anterior.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
010110
Complejidad temporal: O(A*B)
Espacio auxiliar: O(A*B)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA