Encuentre la cantidad de palabras de M caracteres que tienen al menos un carácter repetido

Dados dos números enteros N y M , la tarea es contar el total de palabras de M caracteres de longitud formadas por los N caracteres distintos dados, de modo que las palabras tengan al menos un carácter repetido más de una vez.
Ejemplos: 
 

Entrada: N = 3, M = 2 
Salida: 3 
Supongamos que los caracteres son {‘a’, ‘b’, ‘c’} 
Las 2 palabras de longitud que se pueden formar con estos caracteres 
son “aa”, “ab”, “ ac”, “ba”, “bb”, “bc”, “ca”, “cb” y “cc”. 
De estas palabras, solo «aa», «bb» y «cc» tienen 
al menos un carácter repetido más de una vez.
Entrada: N = 10, M = 5 
Salida: 69760 
 

Enfoque: 
Número total de M palabras de caracteres posibles a partir de N caracteres, total = N ^M . 
Número total de M palabras de caracteres posibles a partir de N caracteres donde ningún carácter se repite, noRepeat = ^N P _M . 
Por lo tanto, el total de palabras donde al menos un solo carácter aparece más de una vez es total: noRepeat, es decir , N ^M – ^N P _M .
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation for the above approach
#include <math.h>
#include <iostream>
using namespace std;
 
// Function to return the
// factorial of a number
int fact(int n)
{
    if (n <= 1)
        return 1;
    return n * fact(n - 1);
}
 
// Function to return the value of nPr
int nPr(int n, int r)
{
    return fact(n) / fact(n - r);
}
 
// Function to return the total number of
// M length words which have at least a
// single character repeated more than once
int countWords(int N, int M)
{
    return pow(N, M) - nPr(N, M);
}
 
// Driver code
int main()
{
    int N = 10, M = 5;
    cout << (countWords(N, M));
    return 0;
}
 
// This code is contributed by jit_t

// Java implementation of the approach
class GFG {
 
    // Function to return the
    // factorial of a number
    static int fact(int n)
    {
        if (n <= 1)
            return 1;
        return n * fact(n - 1);
    }
 
    // Function to return the value of nPr
    static int nPr(int n, int r)
    {
        return fact(n) / fact(n - r);
    }
 
    // Function to return the total number of
    // M length words which have at least a
    // single character repeated more than once
    static int countWords(int N, int M)
    {
        return (int)Math.pow(N, M) - nPr(N, M);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 10, M = 5;
        System.out.print(countWords(N, M));
    }
}

# Python3 implementation for the above approach
 
# Function to return the
# factorial of a number
def fact(n):
 
    if (n <= 1):
        return 1;
    return n * fact(n - 1);
 
# Function to return the value of nPr
def nPr(n, r):
 
    return fact(n) // fact(n - r);
 
# Function to return the total number of
# M length words which have at least a
# single character repeated more than once
def countWords(N, M):
 
    return pow(N, M) - nPr(N, M);
 
# Driver code
N = 10; M = 5;
print(countWords(N, M));
 
# This code is contributed by Code_Mech

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the
    // factorial of a number
    static int fact(int n)
    {
        if (n <= 1)
            return 1;
        return n * fact(n - 1);
    }
 
    // Function to return the value of nPr
    static int nPr(int n, int r)
    {
        return fact(n) / fact(n - r);
    }
 
    // Function to return the total number of
    // M length words which have at least a
    // single character repeated more than once
    static int countWords(int N, int M)
    {
        return (int)Math.Pow(N, M) - nPr(N, M);
    }
 
    // Driver code
    static public void Main ()
    {
        int N = 10, M = 5;
        Console.Write(countWords(N, M));
    }
}
 
// This code is contributed by ajit.

// javascript implementation of the approach
 
       
    // Function to return the
    // factorial of a number
     
    function fact(n)
    {
        if (n <= 1)
            return 1;
        return n * fact(n - 1);
    }
   
    // Function to return the value of nPr
     
    function nPr( n,  r)
    {
        return fact(n) / fact(n - r);
    }
   
    // Function to return the total number of
    // M length words which have at least a
    // single character repeated more than once
     
    function countWords( N,  M)
    {
        return Math.pow(N, M) - nPr(N, M);
    }
   
    // Driver code
        var N = 10 ;
        var M = 5;
        document.write(countWords(N, M));
 
  // This code is contributed by bunnyram19.

69760

Complejidad de tiempo: O(n)

Espacio auxiliar: O(1), el espacio de la pila de llamadas no se considera aquí