Dados dos enteros positivos N y M , la tarea es calcular el número de strings no palindrómicas de longitud M utilizando los N caracteres distintos dados.
Nota: cada carácter distinto se puede utilizar más de una vez.
Ejemplos:
Entrada: N = 3, M = 2
Salida: 6
Explicación:
Dado que solo se dan 3 caracteres, esos 3 caracteres se pueden usar para formar 3 2 strings diferentes. De estas, solo 3 cuerdas son palindrómicas. Por lo tanto, las 6 cuerdas restantes son palindrómicas.Entrada: N = 26, M = 5
Salida: 11863800
Enfoque:
siga los pasos a continuación para resolver el problema:
- El número total de strings de longitud M usando N caracteres dados será N M .
- Para que una cuerda sea un palíndromo, la primera mitad y la segunda mitad deben ser iguales. Para valores pares de M , necesitamos seleccionar solo M/2 caracteres de los N caracteres dados. Para valores impares , necesitamos seleccionar M/2 + 1 caracteres de los N caracteres dados. Como se permiten repeticiones, el número total de hilos palindrómicos de longitud M será N (M/2 + M%2) .
- El recuento requerido de cuerdas no palindrómicas viene dado por la siguiente ecuación:
NM - N(M/2 + M%2)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to count
// non-palindromic strings
// of length M using N
// distinct characters
#include <bits/stdc++.h>
using namespace std;
// Iterative Function to calculate
// base^pow in O(log y)
unsigned long long power(
unsigned long long base,
unsigned long long pow)
{
unsigned long long res = 1;
while (pow > 0) {
if (pow & 1)
res = (res * base);
base = (base * base);
pow >>= 1;
}
return res;
}
// Function to return the
// count of non palindromic strings
unsigned long long countNonPalindromicString(
unsigned long long n,
unsigned long long m)
{
// Count of strings using n
// characters with
// repetitions allowed
unsigned long long total
= power(n, m);
// Count of palindromic strings
unsigned long long palindrome
= power(n, m / 2 + m % 2);
// Count of non-palindromic strings
unsigned long long count
= total - palindrome;
return count;
}
int main()
{
int n = 3, m = 5;
cout<< countNonPalindromicString(n, m);
return 0;
}
Java
// Java program to count non-palindromic
// strings of length M using N distinct
// characters
import java.util.*;
class GFG{
// Iterative Function to calculate
// base^pow in O(log y)
static long power(long base, long pow)
{
long res = 1;
while (pow > 0)
{
if ((pow & 1) == 1)
res = (res * base);
base = (base * base);
pow >>= 1;
}
return res;
}
// Function to return the
// count of non palindromic strings
static long countNonPalindromicString(long n,
long m)
{
// Count of strings using n
// characters with
// repetitions allowed
long total = power(n, m);
// Count of palindromic strings
long palindrome = power(n, m / 2 + m % 2);
// Count of non-palindromic strings
long count = total - palindrome;
return count;
}
// Driver code
public static void main(String[] args)
{
int n = 3, m = 5;
System.out.println(
countNonPalindromicString(n, m));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to count non-palindromic strings # of length M using N distinct characters # Iterative Function to calculate # base^pow in O(log y) def power(base, pwr): res = 1 while(pwr > 0): if(pwr & 1): res = res * base base = base * base pwr >>= 1 return res # Function to return the count # of non palindromic strings def countNonPalindromicString(n, m): # Count of strings using n # characters with # repetitions allowed total = power(n, m) # Count of palindromic strings palindrome = power(n, m // 2 + m % 2) # Count of non-palindromic strings count = total - palindrome return count # Driver code if __name__ == '__main__': n = 3 m = 5 print(countNonPalindromicString(n, m)) # This code is contributed by Shivam Singh
C#
// C# program to count non-palindromic
// strings of length M using N distinct
// characters
using System;
class GFG{
// Iterative Function to calculate
// base^pow in O(log y)
static long power(long Base, long pow)
{
long res = 1;
while (pow > 0)
{
if ((pow & 1) == 1)
res = (res * Base);
Base = (Base * Base);
pow >>= 1;
}
return res;
}
// Function to return the
// count of non palindromic strings
static long countNonPalindromicString(long n,
long m)
{
// Count of strings using n
// characters with
// repetitions allowed
long total = power(n, m);
// Count of palindromic strings
long palindrome = power(n, m / 2 + m % 2);
// Count of non-palindromic strings
long count = total - palindrome;
return count;
}
// Driver code
public static void Main(String[] args)
{
int n = 3, m = 5;
Console.WriteLine(
countNonPalindromicString(n, m));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to count non-palindromic
// strings of length M using N distinct
// characters
// Iterative Function to calculate
// base^pow in O(log y)
function power(base, pow)
{
let res = 1;
while (pow > 0)
{
if ((pow & 1) == 1)
res = (res * base);
base = (base * base);
pow >>= 1;
}
return res;
}
// Function to return the
// count of non palindromic strings
function countNonPalindromicString(n, m)
{
// Count of strings using n
// characters with
// repetitions allowed
let total = power(n, m);
// Count of palindromic strings
let palindrome = power(n, m / 2 + m % 2);
// Count of non-palindromic strings
let count = total - palindrome;
return count;
}
// Driver Code
let n = 3, m = 5;
document.write(countNonPalindromicString(n, m));
// This code is contributed by sanjoy_62
</script>
Producción:
216
Complejidad del tiempo: O(log(N))