Dado un número entero N , que representa la longitud de una string, la tarea es contar el número de strings posibles de longitud N que consisten en una sola vocal y una consonante.
Nota: Dado que la salida puede ser en letra grande en módulo 1000000007
Ejemplos:
Entrada: N = 2
Salida: 210
Explicación:
Hay 5 vocales y 21 consonantes en los alfabetos ingleses.
Entonces, para la vocal ‘a’ podemos tener 42 strings de la forma ‘ab’, ‘ba’, ‘ac’, ‘ca’, ‘ad’, ‘da’ y así sucesivamente.
Para las otras 4 vocales, se repite el mismo proceso y obtenemos un total de 210 strings de este tipo.
Entrada: N = 3
Salida: 8190
Enfoque:
para resolver el problema mencionado anteriormente, debemos ignorar las strings que comprenden solo vocales (para permitir al menos una consonante) y solo consonantes (para permitir al menos una vocal). Por lo tanto, la respuesta requerida es:
Todas las strings de longitud N posibles – (strings de longitud N que consisten solo en vocales + strings de longitud N que consisten solo en consonantes) = 26 N – (5 N + 21 N )
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count all // possible strings of length N // consisting of atleast one // vowel and one consonant #include <bits/stdc++.h> using namespace std; const unsigned long long mod = 1e9 + 7; // Function to return base^exponent unsigned long long expo( unsigned long long base, unsigned long long exponent) { unsigned long long ans = 1; while (exponent != 0) { if ((exponent & 1) == 1) { ans = ans * base; ans = ans % mod; } base = base * base; base %= mod; exponent >>= 1; } return ans % mod; } // Function to count all possible strings unsigned long long findCount( unsigned long long N) { // All possible strings of length N unsigned long long ans = (expo(26, N) // vowels only - expo(5, N) // consonants only - expo(21, N)) % mod; ans += mod; ans %= mod; // Return the // final result return ans; } // Driver Program int main() { unsigned long long N = 3; cout << findCount(N); return 0; }
Java
// Java program to count all // possible Strings of length N // consisting of atleast one // vowel and one consonant class GFG{ static int mod = (int) (1e9 + 7); // Function to return base^exponent static int expo(int base, int exponent) { int ans = 1; while (exponent != 0) { if ((exponent & 1) == 1) { ans = ans * base; ans = ans % mod; } base = base * base; base %= mod; exponent >>= 1; } return ans % mod; } // Function to count all possible Strings static int findCount(int N) { // All possible Strings of length N int ans = (expo(26, N) - // Vowels only expo(5, N) - // Consonants only expo(21, N))% mod; ans += mod; ans %= mod; // Return the // final result return ans; } // Driver code public static void main(String[] args) { int N = 3; System.out.print(findCount(N)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to count all # possible strings of length N # consisting of atleast one # vowel and one consonant mod = 1e9 + 7 # Function to return base^exponent def expo(base, exponent): ans = 1 while (exponent != 0): if ((exponent & 1) == 1): ans = ans * base ans = ans % mod base = base * base base %= mod exponent >>= 1 return ans % mod # Function to count all # possible strings def findCount(N): # All possible strings # of length N ans = ((expo(26, N) - # vowels only expo(5, N) - # consonants only expo(21, N)) % mod) ans += mod ans %= mod # Return the # final result return ans # Driver Program if __name__ == "__main__": N = 3 print (int(findCount(N))) # This code is contributed by Chitranayal
C#
// C# program to count all possible Strings // of length N consisting of atleast one // vowel and one consonant using System; class GFG{ static int mod = (int)(1e9 + 7); // Function to return base^exponent static int expo(int Base, int exponent) { int ans = 1; while (exponent != 0) { if ((exponent & 1) == 1) { ans = ans * Base; ans = ans % mod; } Base = Base * Base; Base %= mod; exponent >>= 1; } return ans % mod; } // Function to count all possible Strings static int findCount(int N) { // All possible Strings of length N int ans = (expo(26, N) - // Vowels only expo(5, N) - // Consonants only expo(21, N)) % mod; ans += mod; ans %= mod; // Return the // readonly result return ans; } // Driver code public static void Main(String[] args) { int N = 3; Console.Write(findCount(N)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program to count all // possible Strings of length N // consisting of atleast one // vowel and one consonant var mod = parseInt( 1e9 + 7); // Function to return base^exponent function expo(base , exponent) { var ans = 1; while (exponent != 0) { if ((exponent & 1) == 1) { ans = ans * base; ans = ans % mod; } base = base * base; base %= mod; exponent >>= 1; } return ans % mod; } // Function to count all possible Strings function findCount(N) { // All possible Strings of length N var ans = (expo(26, N) - // Vowels only expo(5, N) - // Consonants only expo(21, N)) % mod; ans += mod; ans %= mod; // Return the // final result return ans; } // Driver code var N = 3; document.write(findCount(N)); // This code is contributed by todaysgaurav </script>
8190
Complejidad de tiempo: O (log 10 N)
Espacio Auxiliar: O(1)