Dados dos números enteros N y K , la tarea es encontrar el número de strings binarias de una longitud máxima de N que se pueden formar de modo que el número de unos consecutivos sea siempre un múltiplo de K.
Ejemplo:
Entrada: N = 3, K = 2
Salida: 6
Explicación: Las strings binarias de al menos N longitud que contienen 1 consecutivos como múltiplo de K son las siguientes:
- Longitud 1: “0”, contiene 0 1 consecutivos.
- Longitud 2: “00”, “11”, contiene 0 y 2 1 consecutivos respectivamente.
- Longitud 3: “000”, “011”, “110”, contiene 0 y dos combinaciones diferentes de 2 1 consecutivos respectivamente.
Entonces, el número total de strings que se pueden formar es 6.
Entrada: N = 5, K = 4
Salida: 8
Enfoque: El problema dado se puede resolver con la ayuda de la Programación Dinámica usando memorización . Siga los pasos a continuación para resolver el problema dado:
- Cree una función recursiva cntStrings(N, K) , que devuelve el número de strings de N longitud que tienen los 1 consecutivos como múltiplos de K . Esto se puede hacer asignando 1 a los siguientes K índices consecutivos del índice actual y llamando recursivamente a la string restante o asignando 0 al índice actual y llamando recursivamente a la string restante.
- Cree una array dp[] que almacene los valores memorizados de la función recursiva anterior.
- Llame a la función cntStrings(i, K) para todos los valores posibles de i en el rango [1, N] y almacene su suma en una variable cnt .
- El valor almacenado en cnt es la respuesta requerida.
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;
int dp[1001];
// Recursive function to find the count
// of valid binary strings of length n
int cntString(int n, int k)
{
// Base Case
if (n == 0) {
return 1;
}
// If current value is already calculated
if (dp[n] != -1) {
return dp[n];
}
// Stores the current answer
int ans = 0;
// Case for element at next k indices as 1
if (n >= k) {
ans += cntString(n - k, k);
}
// Case for element at current index as 0
ans += cntString(n - 1, k);
// Return ans with storing it in dp[]
return dp[n] = ans;
}
// Function to find the count of valid
// binary strings of atmost N length
int cntStringAll(int N, int K)
{
// Initializing all elements with -1
memset(dp, -1, sizeof(dp));
// Stores the final answer
int cnt = 0;
// Iterate and calculate the total
// possible binary strings of each
// length in the range [1, N]
for (int i = 1; i <= N; i++) {
cnt += cntString(i, K);
}
// Return Answer
return cnt;
}
// Driver Code
int main()
{
int N = 5;
int K = 4;
cout << cntStringAll(N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
static int dp[] = new int[1001];
// Recursive function to find the count
// of valid binary strings of length n
static int cntString(int n, int k)
{
// Base Case
if (n == 0) {
return 1;
}
// If current value is already calculated
if (dp[n] != -1) {
return dp[n];
}
// Stores the current answer
int ans = 0;
// Case for element at next k indices as 1
if (n >= k) {
ans += cntString(n - k, k);
}
// Case for element at current index as 0
ans += cntString(n - 1, k);
// Return ans with storing it in dp[]
return dp[n] = ans;
}
// Function to find the count of valid
// binary strings of atmost N length
static int cntStringAll(int N, int K)
{
// Initializing all elements with -1
for (int i = 0; i < 1001; i++)
dp[i] = -1;
// Stores the final answer
int cnt = 0;
// Iterate and calculate the total
// possible binary strings of each
// length in the range [1, N]
for (int i = 1; i <= N; i++) {
cnt += cntString(i, K);
}
// Return Answer
return cnt;
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int K = 4;
System.out.println(cntStringAll(N, K));
}
}
// This code is contributed by dwivediyash
Python3
# python program for the above approach dp = [-1 for _ in range(1001)] # Recursive function to find the count # of valid binary strings of length n def cntString(n, k): # Base Case if (n == 0): return 1 # If current value is already calculated if (dp[n] != -1): return dp[n] # Stores the current answer ans = 0 # Case for element at next k indices as 1 if (n >= k): ans += cntString(n - k, k) # Case for element at current index as 0 ans += cntString(n - 1, k) # Return ans with storing it in dp[] dp[n] = ans return dp[n] # Function to find the count of valid # binary strings of atmost N length def cntStringAll(N, K): # Stores the final answer cnt = 0 # Iterate and calculate the total # possible binary strings of each # length in the range [1, N] for i in range(1, N + 1): cnt += cntString(i, K) # Return Answer return cnt # Driver Code if __name__ == "__main__": N = 5 K = 4 print(cntStringAll(N, K)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
public class GFG
{
static int []dp = new int[1001];
// Recursive function to find the count
// of valid binary strings of length n
static int cntString(int n, int k)
{
// Base Case
if (n == 0) {
return 1;
}
// If current value is already calculated
if (dp[n] != -1) {
return dp[n];
}
// Stores the current answer
int ans = 0;
// Case for element at next k indices as 1
if (n >= k) {
ans += cntString(n - k, k);
}
// Case for element at current index as 0
ans += cntString(n - 1, k);
// Return ans with storing it in dp[]
return dp[n] = ans;
}
// Function to find the count of valid
// binary strings of atmost N length
static int cntStringAll(int N, int K)
{
// Initializing all elements with -1
for (int i = 0; i < 1001; i++)
dp[i] = -1;
// Stores the final answer
int cnt = 0;
// Iterate and calculate the total
// possible binary strings of each
// length in the range [1, N]
for (int i = 1; i <= N; i++) {
cnt += cntString(i, K);
}
// Return Answer
return cnt;
}
// Driver Code
public static void Main(String[] args)
{
int N = 5;
int K = 4;
Console.WriteLine(cntStringAll(N, K));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
let dp = new Array(1001).fill(-1);
// Recursive function to find the count
// of valid binary strings of length n
const cntString = (n, k) => {
// Base Case
if (n == 0) {
return 1;
}
// If current value is already calculated
if (dp[n] != -1) {
return dp[n];
}
// Stores the current answer
let ans = 0;
// Case for element at next k indices as 1
if (n >= k) {
ans += cntString(n - k, k);
}
// Case for element at current index as 0
ans += cntString(n - 1, k);
// Return ans with storing it in dp[]
return dp[n] = ans;
}
// Function to find the count of valid
// binary strings of atmost N length
const cntStringAll = (N, K) => {
// Stores the final answer
let cnt = 0;
// Iterate and calculate the total
// possible binary strings of each
// length in the range [1, N]
for (let i = 1; i <= N; i++) {
cnt += cntString(i, K);
}
// Return Answer
return cnt;
}
// Driver Code
let N = 5;
let K = 4;
document.write(cntStringAll(N, K));
// This code is contributed by rakeshsahni
</script>
Producción
8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)