Dado un entero positivo N , la tarea es encontrar el número de strings palindrómicas alfanuméricas de longitud N . Dado que el conteo de dichas strings puede ser muy grande, imprima la respuesta módulo 10 9 + 7 .
Ejemplos:
Entrada: N = 2
Salida: 62
Explicación: Hay 26 palíndromos de la forma {“AA”, “BB”, …, “ZZ”}, 26 palíndromos de la forma {“aa”, “bb”, …, “ cc”} y 10 palíndromos de la forma {“00”, “11”, …, “99”}. Por lo tanto, el número total de hilos palindrómicos = 26 + 26 + 10 = 62.Entrada: N = 3
Salida: 3844
Enfoque ingenuo: el enfoque más simple es generar todas las strings alfanuméricas posibles de longitud N y, para cada string, verificar si es un palíndromo o no . Ya que, en cada posición, se pueden colocar 62 caracteres en total. Por lo tanto, hay 62 N strings posibles.
Complejidad temporal: O(N*62 N )
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la propiedad de palíndromo . Se puede observar que si la longitud de la string es par , entonces para cada índice i de 0 a N/2 , los caracteres en los índices i y (N – 1 – i) son los mismos. Por lo tanto, para cada posición de 0 a N/2 hay 62 N/2 opciones. Del mismo modo, si la longitud es impar, hay 62 (N+1)/2 opciones. Por tanto, se puede decir que, para algún N , hay 62 ceil(N/2) posiblescuerdas palindrómicas .
Siga los pasos a continuación para resolver el problema:
- Para el valor dado de N , calcule 62 ceil(N/2) mod 10 9 + 7 usando Modular Exponentiation .
- Imprima 62 ceil(N/2) mod 10 9 + 7 como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// (x ^ y) mod p
int power(int x, int y,
int p)
{
// Initialize result
int res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
// Return the final
// result
return res;
}
// Driver Code
int main()
{
// Given N
int N = 3;
int flag, k, m;
// Base Case
if((N == 1) ||
(N == 2))
cout << 62;
else
m = 1000000000 + 7;
// Check whether n
// is even or odd
if(N % 2 == 0)
{
k = N / 2;
flag = true;
}
else
{
k = (N - 1) / 2;
flag = false;
}
if(flag != 0)
{
// Function Call
int a = power(62,
k, m);
cout << a;
}
else
{
// Function Call
int a = power(62,
(k + 1), m);
cout << a;
}
}
// This code is contributed by sanjoy_62
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to calculate
// (x ^ y) mod p
static int power(int x,
int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
// Return the final
// result
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given N
int N = 3;
int flag, k, m =0;
// Base Case
if ((N == 1) || (N == 2))
System.out.print(62);
else
m = 1000000000 + 7;
// Check whether n
// is even or odd
if (N % 2 == 0)
{
k = N / 2;
flag = 1;
}
else
{
k = (N - 1) / 2;
flag = 0;
}
if (flag != 0)
{
// Function Call
int a = power(62, k, m);
System.out.print(a);
}
else
{
// Function Call
int a = power(62, (k + 1), m);
System.out.print(a);
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to calculate (x ^ y) mod p def power(x, y, p): # Initialize result res = 1 # Update x if it is more # than or equal to p x = x % p if (x == 0): return 0 while (y > 0): # If y is odd, multiply # x with result if ((y & 1) == 1): res = (res * x) % p # y must be even now y = y >> 1 x = (x * x) % p # Return the final result return res # Driver Code # Given N N = 3 # Base Case if((N == 1) or (N == 2)): print(62) else: m = (10**9)+7 # Check whether n # is even or odd if(N % 2 == 0): k = N//2 flag = True else: k = (N - 1)//2 flag = False if(flag): # Function Call a = power(62, k, m) print(a) else: # Function Call a = power(62, (k + 1), m) print(a)
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to calculate
// (x ^ y) mod p
static int power(int x, int y,
int p)
{
// Initialize result
int res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
// Return the final
// result
return res;
}
// Driver Code
public static void Main()
{
// Given N
int N = 3;
int flag, k, m = 0;
// Base Case
if ((N == 1) || (N == 2))
Console.Write(62);
else
m = 1000000000 + 7;
// Check whether n
// is even or odd
if (N % 2 == 0)
{
k = N / 2;
flag = 1;
}
else
{
k = (N - 1) / 2;
flag = 0;
}
if (flag != 0)
{
// Function Call
int a = power(62, k, m);
Console.Write(a);
}
else
{
// Function Call
int a = power(62, (k + 1), m);
Console.Write(a);
}
}
}
// This code is contributed by code_hunt
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to calculate
// (x ^ y) mod p
function power(x, y, p)
{
// Initialize result
let res = 1;
// Update x if it is more
// than or equal to p
x = x % p;
if (x == 0)
return 0;
while (y > 0)
{
// If y is odd, multiply
// x with result
if ((y & 1) == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1;
x = (x * x) % p;
}
// Return the final
// result
return res;
}
// Driver Code
// Given N
let N = 3;
let flag, k, m =0;
// Base Case
if ((N == 1) || (N == 2))
document.write(62);
else
m = 1000000000 + 7;
// Check whether n
// is even or odd
if (N % 2 == 0)
{
k = N / 2;
flag = 1;
}
else
{
k = (N - 1) / 2;
flag = 0;
}
if (flag != 0)
{
// Function Call
let a = power(62, k, m);
document.write(a);
}
else
{
// Function Call
let a = power(62, (k + 1), m);
document.write(a);
}
</script>
3844
Complejidad temporal: O(log N)
Espacio auxiliar: O(N)