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):
- “0000”: Esta string es la concatenación repetida de la substring “0”.
- “1111”: Esta string es la concatenación repetida de la substring “1”.
- “0101”: Esta string es la concatenación repetida de la substring “01”.
- “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>
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