Conteo de strings binarias de longitud N con un conteo de bits parejo y como máximo K 1s consecutivos

Dados dos números enteros N y K , la tarea es encontrar el número de strings binarias de longitud N que tienen un número par de 1, de las cuales menos de K son consecutivas.
Ejemplos:

Entrada: N = 4, K = 2
Salida: 4
Explicación:
Las strings binarias posibles son 0000, 0101, 1001, 1010. Todas tienen un número par de 1 con menos de 2 de ellos consecutivos.
Entrada: N = 3, K = 2
Salida: 2
Explicación:
Las posibles strings binarias son 000, 101. Todas las demás strings que son 001, 010, 011, 100, 110, 111 no cumplen los criterios.

Enfoque:
Este problema se puede resolver mediante Programación Dinámica.
Consideremos una tabla 3D dp[][][] para almacenar la solución de cada subproblema, tal que, dp[n][i][s] denota el número de strings binarias de longitud n que tienen i 1 consecutivos y la suma de 1 = s . Como solo se requiere verificar si el número total de 1 es par o no, almacenamos s% 2 . Entonces, dp[n][i][s] se puede calcular de la siguiente manera:

Si colocamos 0 en la n ^-ésima posición , el número de 1 permanece sin cambios. Por lo tanto, dp[n][i][s] = dp[n – 1][0][s] .
Si colocamos 1 en la n ^-ésima posición , dp[n][i][s] = dp[n – 1][i + 1][(s + 1) % 2] .
A partir de los dos puntos anteriores, la relación de recurrencia formada viene dada por:

$dp[n][i][s] = dp[n-1][0][s] + dp[n - 1][i + 1][(s + 1)mod 2]$

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;
 
// Table to store solution
// of each subproblem
int dp[100001][20][2];
 
// Function to calculate
// the possible binary
// strings
int possibleBinaries(int pos,
                     int ones,
                     int sum,
                     int k)
{
    // If number of ones
    // is equal to K
    if (ones == k)
        return 0;
 
    // pos: current position
    // Base Case: When n
    // length is traversed
    if (pos == 0)
 
        // sum: count of 1's
        // Return the count
        // of 1's obtained
        return (sum == 0) ? 1 : 0;
 
    // If the subproblem has already
    // been solved
    if (dp[pos][ones][sum] != -1)
        // Return the answer
        return dp[pos][ones][sum];
 
    // Recursive call when current
    // position is filled with 1
    int ret = possibleBinaries(pos - 1,
                               ones + 1,
                               (sum + 1) % 2,
                               k)
              // Recursive call when current
              // position is filled with 0
              + possibleBinaries(pos - 1, 0,
                                 sum, k);
 
    // Store the solution
    // to this subproblem
    dp[pos][ones][sum] = ret;
 
    return dp[pos][ones][sum];
}
 
// Driver Code
int main()
{
    int N = 3;
    int K = 2;
 
    // Initialising the
    // table with -1
    memset(dp, -1, sizeof dp);
 
    cout << possibleBinaries(N, 0, 0, K);
}

Java

// Java program for the above approach
class GFG{
 
// Table to store solution
// of each subproblem
static int [][][]dp = new int[100001][20][2];
 
// Function to calculate
// the possible binary
// Strings
static int possibleBinaries(int pos, int ones,
                            int sum, int k)
{
     
    // If number of ones
    // is equal to K
    if (ones == k)
        return 0;
 
    // pos: current position
    // Base Case: When n
    // length is traversed
    if (pos == 0)
 
        // sum: count of 1's
        // Return the count
        // of 1's obtained
        return (sum == 0) ? 1 : 0;
 
    // If the subproblem has already
    // been solved
    if (dp[pos][ones][sum] != -1)
     
        // Return the answer
        return dp[pos][ones][sum];
 
    // Recursive call when current
    // position is filled with 1
    int ret = possibleBinaries(pos - 1,
                              ones + 1,
                              (sum + 1) % 2, k) +
                               
              // Recursive call when current
              // position is filled with 0
              possibleBinaries(pos - 1, 0,
                               sum, k);
                                
    // Store the solution
    // to this subproblem
    dp[pos][ones][sum] = ret;
 
    return dp[pos][ones][sum];
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
    int K = 2;
 
    // Initialising the
    // table with -1
    for(int i = 0; i < 100001; i++)
    {
        for(int j = 0; j < 20; j++)
        {
            for(int l = 0; l < 2; l++)
                dp[i][j][l] = -1;
        }
    }
 
    System.out.print(possibleBinaries(N, 0, 0, K));
}
}
 
// This code is contributed by Rohit_ranjan

Python3

# Python3 program for the above approach
import numpy as np
 
# Table to store solution
# of each subproblem
dp = np.ones(((100002, 21, 3)))
dp = -1 * dp
 
# Function to calculate
# the possible binary
# strings
def possibleBinaries(pos, ones, sum, k):
     
    # If number of ones
    # is equal to K
    if (ones == k):
        return 0
 
    # pos: current position
    # Base Case: When n
    # length is traversed
    if (pos == 0):
 
        # sum: count of 1's
        # Return the count
        # of 1's obtained
        return 1 if (sum == 0) else 0
 
    # If the subproblem has already
    # been solved
    if (dp[pos][ones][sum] != -1):
         
        # Return the answer
        return dp[pos][ones][sum]
 
    # Recursive call when current
    # position is filled with 1
    ret = (possibleBinaries(pos - 1,
                           ones + 1,
                           (sum + 1) % 2, k) +
     
           # Recursive call when current
           # position is filled with 0
           possibleBinaries(pos - 1, 0, sum, k))
 
    # Store the solution
    # to this subproblem
    dp[pos][ones][sum] = ret
 
    return dp[pos][ones][sum]
 
# Driver Code
N = 3
K = 2
             
print(int(possibleBinaries(N, 0, 0, K)))
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Table to store solution
// of each subproblem
static int [,,]dp = new int[100001, 20, 2];
 
// Function to calculate the
// possible binary Strings
static int possibleBinaries(int pos, int ones,
                            int sum, int k)
{
     
    // If number of ones
    // is equal to K
    if (ones == k)
        return 0;
 
    // pos: current position
    // Base Case: When n
    // length is traversed
    if (pos == 0)
 
        // sum: count of 1's
        // Return the count
        // of 1's obtained
        return (sum == 0) ? 1 : 0;
 
    // If the subproblem has already
    // been solved
    if (dp[pos, ones, sum] != -1)
     
        // Return the answer
        return dp[pos, ones, sum];
 
    // Recursive call when current
    // position is filled with 1
    int ret = possibleBinaries(pos - 1,
                                ones + 1,
                                (sum + 1) % 2, k) +
              // Recursive call when current
              // position is filled with 0
              possibleBinaries(pos - 1, 0,
                               sum, k);
                                
    // Store the solution
    // to this subproblem
    dp[pos, ones, sum] = ret;
 
    return dp[pos, ones, sum];
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 3;
    int K = 2;
 
    // Initialising the
    // table with -1
    for(int i = 0; i < 100001; i++)
    {
        for(int j = 0; j < 20; j++)
        {
            for(int l = 0; l < 2; l++)
                dp[i, j, l] = -1;
        }
    }
    Console.Write(possibleBinaries(N, 0, 0, K));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
// Javascript program for the above approach
 
// Table to store solution
// of each subproblem
let dp = new Array(100001).fill(-1).map((t) => new Array(20).fill(-1).map((r) => new Array(2).fill(-1)));
 
// Function to calculate
// the possible binary
// strings
function possibleBinaries(pos, ones, sum, k)
{
 
    // If number of ones
    // is equal to K
    if (ones == k)
        return 0;
 
    // pos: current position
    // Base Case: When n
    // length is traversed
    if (pos == 0)
 
        // sum: count of 1's
        // Return the count
        // of 1's obtained
        return (sum == 0) ? 1 : 0;
 
    // If the subproblem has already
    // been solved
    if (dp[pos][ones][sum] != -1)
        // Return the answer
        return dp[pos][ones][sum];
 
    // Recursive call when current
    // position is filled with 1
    let ret = possibleBinaries(pos - 1,
        ones + 1,
        (sum + 1) % 2,
        k)
         
        // Recursive call when current
        // position is filled with 0
        + possibleBinaries(pos - 1, 0,
            sum, k);
 
    // Store the solution
    // to this subproblem
    dp[pos][ones][sum] = ret;
 
    return dp[pos][ones][sum];
}
 
// Driver Code
let N = 3;
let K = 2;
 
// Initialising the
// table with -1
document.write(possibleBinaries(N, 0, 0, K));
 
// This code is contributed by _saurabh_jaiswal
</script>

Producción:

Complejidad de tiempo: O(2*N*K), donde N y K representan los dos enteros dados.
Espacio auxiliar: O ( 100001*20*2 ), no se requiere ningún otro espacio adicional, por lo que es una constante.

Publicación traducida automáticamente

Artículo escrito por webhead y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta