Dada una string str y dos enteros P y Q . La tarea es encontrar el recuento total de palabras que se pueden formar eligiendo exactamente P consonantes y Q vocales de la string dada.
Ejemplos:
Entrada: str = “geek”, P = 1, Q = 1
Salida: 8
“ge”, “ge”, “eg”, “ek”, “eg”, “ek”,
“ke” y “ke” son las palabras posibles.
Entrada: str = «crackathon», P = 4, Q = 3
Salida: 176400
Enfoque: dado que las consonantes P y las vocales Q deben elegirse del recuento original de consonantes y vocales en la string dada. Entonces, el coeficiente binomial se puede usar para calcular las combinaciones de elegir estos caracteres y los caracteres elegidos se pueden organizar en sí mismos usando el factorial de su cuenta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define lli long long int // Function to return the value of nCk lli binomialCoeff(lli n, lli k) { if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } // Function to return the factorial of n lli fact(lli n) { if (n >= 1) return n * fact(n - 1); else return 1; } // Function that returns true if ch is a vowel bool isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // Function to return the number of words possible lli countWords(string s, int p, int q) { // To store the count of vowels and // consonanats in the given string lli countc = 0, countv = 0; for (int i = 0; i < s.length(); i++) { // If current character is a vowel if (isVowel(s[i])) countv++; else countc++; } // Find the total possible words lli a = binomialCoeff(countc, p); lli b = binomialCoeff(countv, q); lli c = fact(p + q); lli ans = (a * b) * c; return ans; } // Driver code int main() { string s = "crackathon"; int p = 4, q = 3; cout << countWords(s, p, q); return 0; }
Java
// Java implementation of the above approach class GFG { // Function to return the value of nCk static long binomialCoeff(long n, long k) { if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } // Function to return the factorial of n static long fact(long n) { if (n >= 1) return n * fact(n - 1); else return 1; } // Function that returns true if ch is a vowel static boolean isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // Function to return the number of words possible static long countWords(String s, int p, int q) { // To store the count of vowels and // consonanats in the given string long countc = 0, countv = 0; for (int i = 0; i < s.length(); i++) { // If current character is a vowel if (isVowel(s.charAt(i))) countv++; else countc++; } // Find the total possible words long a = binomialCoeff(countc, p); long b = binomialCoeff(countv, q); long c = fact(p + q); long ans = (a * b) * c; return ans; } // Driver code public static void main (String[] args) { String s = "crackathon"; int p = 4, q = 3; System.out.println(countWords(s, p, q)); } } // This Code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the value of nCk def binomialCoeff(n, k): if (k == 0 or k == n): return 1 return binomialCoeff(n - 1, k - 1) + \ binomialCoeff(n - 1, k) # Function to return the factorial of n def fact(n): if (n >= 1): return n * fact(n - 1) else: return 1 # Function that returns true if ch is a vowel def isVowel(ch): if (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u'): return True return False # Function to return the number of words possible def countWords(s, p, q): # To store the count of vowels and # consonanats in the given string countc = 0 countv = 0 for i in range(len(s)): # If current character is a vowel if (isVowel(s[i])): countv += 1 else: countc += 1 # Find the total possible words a = binomialCoeff(countc, p) b = binomialCoeff(countv, q) c = fact(p + q) ans = (a * b) * c return ans # Driver code s = "crackathon" p = 4 q = 3 print(countWords(s, p, q)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to return the value of nCk static long binomialCoeff(long n, long k) { if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } // Function to return the factorial of n static long fact(long n) { if (n >= 1) return n * fact(n - 1); else return 1; } // Function that returns true if ch is a vowel static bool isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // Function to return the number of words possible static long countWords(String s, int p, int q) { // To store the count of vowels and // consonanats in the given string long countc = 0, countv = 0; for (int i = 0; i < s.Length; i++) { // If current character is a vowel if (isVowel(s[i])) countv++; else countc++; } // Find the total possible words long a = binomialCoeff(countc, p); long b = binomialCoeff(countv, q); long c = fact(p + q); long ans = (a * b) * c; return ans; } // Driver code public static void Main (String[] args) { String s = "crackathon"; int p = 4, q = 3; Console.WriteLine(countWords(s, p, q)); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript implementation of the approach // Function to return the value of nCk function binomialCoeff(n, k) { if (k == 0 || k == n) return 1; return binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k); } // Function to return the factorial of n function fact(n) { if (n >= 1) return n * fact(n - 1); else return 1; } // Function that returns true if ch is a vowel function isVowel(ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') { return true; } return false; } // Function to return the number of words possible function countWords(s, p, q) { // To store the count of vowels and // consonanats in the given string var countc = 0, countv = 0; for (var i = 0; i < s.length; i++) { // If current character is a vowel if (isVowel(s[i])) countv++; else countc++; } // Find the total possible words var a = binomialCoeff(countc, p); var b = binomialCoeff(countv, q); var c = fact(p + q); var ans = (a * b) * c; return ans; } // Driver code var s = "crackathon"; var p = 4, q = 3; document.write(countWords(s, p, q)); </script>
176400
Complejidad temporal: O(2 n )
Espacio auxiliar: O(n)