Recuento de strings binarias de longitud N que son concatenaciones repetidas de una substring

Dado un entero positivo N , la tarea es encontrar el número de strings binarias de longitud N que se repiten en la concatenación de una sola substring de esa string.

Ejemplos:

Entrada: N = 4
Salida: 4
Explicación:
A continuación se muestran las posibles strings binarias de longitud N(= 4):

  1. “0000”: Esta string es la concatenación repetida de la substring “0”.
  2. “1111”: Esta string es la concatenación repetida de la substring “1”.
  3. “0101”: Esta string es la concatenación repetida de la substring “01”.
  4. “1010”: Esta string es la concatenación repetida de la substring “10”.

Por lo tanto, el recuento total de dicha string es 4. Por lo tanto, imprima 4.

Entrada: N = 10
Salida: 34

Enfoque: el problema dado se puede resolver en función de la observación de que cada string posible tiene una substring repetida que se concatenó, digamos , K veces, luego la longitud dada de la string N debe ser divisible por K para generar toda la string resultante.

Por lo tanto, encuentre todos los divisores posibles de N y para cada divisor, digamos K , encuentre la cuenta de todas las strings posibles que puede formar cuya concatenación sea la string resultante y esta cuenta se puede calcular por 2 K . Ahora, también se debe restar la cantidad de strings que se repiten entre ellas, por lo tanto, realice la misma operación en el divisor K y réstelo de 2 K para obtener el recuento total de cada llamada recursiva .

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;
 
// Store the recurring recursive states
map<int, int> dp;
 
// Function to find the number of
// strings of length N such that it
// is a concatenation it substrings
int countStrings(int N)
{
     
    // Single character cant be repeated
    if (N == 1)
        return 0;
     
    // Check if this state has been
    // already calculated
    if (dp.find(N) != dp.end())
        return dp[N];
     
    // Stores the resultant count for
    // the current recursive calls
    int ret = 0;
     
    // Iterate over all divisors
    for(int div = 1; div <= sqrt(N); div++)
    {
        if (N % div == 0)
        {
             
            // Non-Repeated = Total - Repeated
            ret += (1 << div) -  countStrings(div);
             
            int div2 = N/div;
             
            if (div2 != div and div != 1)
                 
                // Non-Repeated = Total - Repeated
                ret += (1 << div2) -  countStrings(div2);
        }
    }
     
    // Store the result for the
    // further calculation
    dp[N] = ret;       
                 
    // Return resultant count
    return ret;
}
 
// Driver code
int main()
{
    int N = 6;
     
    // Function Call
    cout << countStrings(N) << endl;
}
 
// This code is contributed by ipg2016107

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Store the recurring recursive states
static HashMap<Integer,
               Integer> dp = new HashMap<Integer,
                                         Integer>();
 
// Function to find the number of
// strings of length N such that it
// is a concatenation it substrings
static int countStrings(int N)
{
     
    // Single character cant be repeated
    if (N == 1)
        return 0;
     
    // Check if this state has been
    // already calculated
    if (dp.containsKey(N))
        return dp.get(N);
     
    // Stores the resultant count for
    // the current recursive calls
    int ret = 0;
     
    // Iterate over all divisors
    for(int div = 1; div <= Math.sqrt(N); div++)
    {
        if (N % div == 0)
        {
             
            // Non-Repeated = Total - Repeated
            ret += (1 << div) -  countStrings(div);
             
            int div2 = N / div;
             
            if (div2 != div && div != 1)
                 
                // Non-Repeated = Total - Repeated
                ret += (1 << div2) -  countStrings(div2);
        }
    }
     
    // Store the result for the
    // further calculation
    dp.put(N, ret);       
                 
    // Return resultant count
    return ret;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 6;
     
    // Function Call
    System.out.print(countStrings(N));
}
}
 
// This code is contributed by code_hunt

Python3

# Python program for the above approach
 
# Store the recurring recursive states
dp = {}
 
# Function to find the number of
# strings of length N such that it
# is a concatenation it substrings
def countStrings(N):
    
    # Single character cant be repeated
    if N == 1:
        return 0
     
    # Check if this state has been
    # already calculated
    if dp.get(N, -1) != -1:
        return dp[N]
     
    # Stores the resultant count for
    # the current recursive calls
    ret = 0
     
    # Iterate over all divisors
    for div in range(1, int(N**.5)+1): 
        if N % div == 0:
             
            # Non-Repeated = Total - Repeated
            ret += (1 << div) -  countStrings(div)
             
            div2 = N//div
             
            if div2 != div and div != 1:
                 
                # Non-Repeated = Total - Repeated
                ret += (1 << div2) -  countStrings(div2)
     
    # Store the result for the
    # further calculation
    dp[N] = ret         
                 
    # Return resultant count
    return ret
 
# Driver Code
N = 6
 
# Function Call
print(countStrings(N))

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Store the recurring recursive states
static Dictionary<int, int> dp = new Dictionary<int, int>();
 
// Function to find the number of
// strings of length N such that it
// is a concatenation it substrings
static int countStrings(int N)
{
     
    // Single character cant be repeated
    if (N == 1)
        return 0;
     
    // Check if this state has been
    // already calculated
    if (dp.ContainsKey(N))
        return dp[N];
     
    // Stores the resultant count for
    // the current recursive calls
    int ret = 0;
     
    // Iterate over all divisors
    for(int div = 1; div <= Math.Sqrt(N); div++)
    {
        if (N % div == 0)
        {
             
            // Non-Repeated = Total - Repeated
            ret += (1 << div) -  countStrings(div);
             
            int div2 = N / div;
             
            if (div2 != div && div != 1)
                 
                // Non-Repeated = Total - Repeated
                ret += (1 << div2) -  countStrings(div2);
        }
    }
     
    // Store the result for the
    // further calculation
    dp[N] = ret;     
                 
    // Return resultant count
    return ret;
}
 
// Driver Code
public static void Main()
{
    int N = 6;
     
    // Function Call
    Console.Write(countStrings(N));
}
}
 
// This code is contributed by splevel62.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Store the recurring recursive states
let dp = new Map();
 
// Function to find the number of
// strings of length N such that it
// is a concatenation it substrings
function countStrings(N) {
  // Single character cant be repeated
  if (N == 1) return 0;
 
  // Check if this state has been
  // already calculated
  if (dp.has(N)) return dp.get(N);
 
  // Stores the resultant count for
  // the current recursive calls
  let ret = 0;
 
  // Iterate over all divisors
  for (let div = 1; div <= Math.sqrt(N); div++) {
    if (N % div == 0) {
      // Non-Repeated = Total - Repeated
      ret += (1 << div) - countStrings(div);
 
      let div2 = N / div;
 
      if (div2 != div && div != 1)
        // Non-Repeated = Total - Repeated
        ret += (1 << div2) - countStrings(div2);
    }
  }
 
  // Store the result for the
  // further calculation
  dp[N] = ret;
 
  // Return resultant count
  return ret;
}
 
// Driver code
 
let N = 6;
 
// Function Call
document.write(countStrings(N) + "<br>");
 
// This code is contributed by _saurabh_jaiswal
 
</script>
Producción: 

10

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *