Dada una palabra en inglés de una longitud máxima de 20 caracteres. Calcula el número de formas de ordenar la palabra de manera que ninguna vocal aparezca junta.
Nota: si el número total de vocales en la palabra dada es uno, entonces el resultado debería ser 0.
Ejemplos:
Input : allahabad Output : 7200 Input : geeksforgeeks Output : 32205600 Input : abcd Output : 0
Ya que la palabra contiene vocales y consonantes. Calcule el número total de formas de organizar la palabra dada y reste el número de formas que tienen todas las vocales juntas. Para calcular el número total de formas, usaremos la siguiente fórmula:
No of ways = (n!) / (r1! * r2! * ... * rk!)
Donde n es el número de caracteres diferentes en la palabra y r1, r2…rk, son la frecuencia de caracteres del mismo tipo.
Para calcular el número de formas en que todas las vocales aparecen juntas, consideramos el grupo de todas las vocales como un solo carácter y, utilizando la fórmula anterior, calcularemos el número total de formas en las que todas las vocales están juntas. Ahora réstelo del número total de formas de obtener el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for above approach #include <bits/stdc++.h> #define ll long long int using namespace std; // Function to check if a character is vowel or consonent bool isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true; else return false; } // Function to calculate factorial of a number ll fact(ll n) { if (n < 2) return 1; return n * fact(n - 1); } // Calculating no of ways for arranging vowels ll only_vowels(map<char, int>& freq) { ll denom = 1; ll cnt_vwl = 0; // Iterate the map and count the number of vowels and calculate // no of ways to arrange vowels for (auto itr = freq.begin(); itr != freq.end(); itr++) { if (isVowel(itr->first)) { denom *= fact(itr->second); cnt_vwl += itr->second; } } return fact(cnt_vwl) / denom; } // calculating no of ways to arrange the given word such that all vowels // come together ll all_vowels_together(map<char, int>& freq) { // calculate no of ways to arrange vowels ll vow = only_vowels(freq); // to store denominator of fraction ll denom = 1; // count of consonents ll cnt_cnst = 0; for (auto itr = freq.begin(); itr != freq.end(); itr++) { if (!isVowel(itr->first)) { denom *= fact(itr->second); cnt_cnst += itr->second; } } // calculate the number of ways to arrange the word such that // all vowels come together ll ans = fact(cnt_cnst + 1) / denom; return (ans * vow); } // To calculate total number of permutations ll total_permutations(map<char, int>& freq) { // To store length of the given word ll cnt = 0; // denominator of fraction ll denom = 1; for (auto itr = freq.begin(); itr != freq.end(); itr++) { denom *= fact(itr->second); cnt += itr->second; } // return total number of permutations of the given word return fact(cnt) / denom; } // Function to calculate number of permutations such that // no vowels come together ll no_vowels_together(string& word) { // to store frequency of character map<char, int> freq; // count frequency of all characters for (int i = 0; i < word.size(); i++) { char ch = tolower(word[i]); freq[ch]++; } // calculate total number of permutations ll total = total_permutations(freq); // calculate total number of permutations such that // all vowels come together ll vwl_tgthr = all_vowels_together(freq); // subtract vwl_tgthr from total to get the result ll res = total - vwl_tgthr; // return the result return res; } // Driver code int main() { string word = "allahabad"; ll ans = no_vowels_together(word); cout << ans << endl; word = "geeksforgeeks"; ans = no_vowels_together(word); cout << ans << endl; word = "abcd"; ans = no_vowels_together(word); cout << ans << endl; return 0; }
Java
// Java code for above approach import java.util.*; import java.lang.*; class GFG { // Function to check if a character // is vowel or consonent static boolean isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true; else return false; } // Function to calculate factorial of a number static long fact(long n) { if (n < 2) { return 1; } return n * fact(n - 1); } // Calculating no of ways for arranging vowels static long only_vowels(HashMap<Character, Integer> freq) { long denom = 1; long cnt_vwl = 0; // Iterate the map and count the number // of vowels and calculate no of ways // to arrange vowels for (Map.Entry<Character, Integer> itr : freq.entrySet()) { if (isVowel(itr.getKey())) { denom *= fact(itr.getValue()); cnt_vwl += itr.getValue(); } } return fact(cnt_vwl) / denom; } // Calculating no of ways to arrange // the given word such that all vowels // come together static long all_vowels_together(HashMap<Character, Integer> freq) { // Calculate no of ways to arrange vowels long vow = only_vowels(freq); // To store denominator of fraction long denom = 1; // Count of consonents long cnt_cnst = 0; for (Map.Entry<Character, Integer> itr : freq.entrySet()) { if (!isVowel(itr.getKey())) { denom *= fact(itr.getValue()); cnt_cnst += itr.getValue(); } } // Calculate the number of ways to // arrange the word such that // all vowels come together long ans = fact(cnt_cnst + 1) / denom; return (ans * vow); } // To calculate total number of permutations static long total_permutations(HashMap<Character, Integer> freq) { // To store length of the given word long cnt = 0; // Denominator of fraction long denom = 1; for (Map.Entry<Character, Integer> itr : freq.entrySet()) { denom *= fact(itr.getValue()); cnt += itr.getValue(); } // Return total number of // permutations of the given word return fact(cnt) / denom; } // Function to calculate number of permutations // such that no vowels come together static long no_vowels_together(String word) { // To store frequency of character HashMap<Character, Integer> freq = new HashMap<>(); // Count frequency of all characters for(int i = 0; i < word.length(); i++) { char ch = Character.toLowerCase(word.charAt(i)); if (freq.containsKey(ch)) { freq.put(ch, freq.get(ch)+1); } else { freq.put(ch, 1); } } // Calculate total number of permutations long total = total_permutations(freq); // Calculate total number of permutations // such that all vowels come together long vwl_tgthr = all_vowels_together(freq); // Subtract vwl_tgthr from total // to get the result long res = total - vwl_tgthr; // Return the result return res; } // Driver code public static void main(String[] args) { String word = "allahabad"; long ans = no_vowels_together(word); System.out.println(ans); word = "geeksforgeeks"; ans = no_vowels_together(word); System.out.println(ans); word = "abcd"; ans = no_vowels_together(word); System.out.println(ans); } } // This code is contributed by divyesh072019
Python3
# Python3 code for above approach # Function to check if a character is # vowel or consonent def isVowel(ch): if (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u') : return True else: return False # Function to calculate factorial of a number def fact(n): if (n < 2): return 1 return n * fact(n - 1) # Calculating no of ways for arranging vowels def only_vowels(freq): denom = 1 cnt_vwl = 0 # Iterate the map and count the number of # vowels and calculate no of ways to arrange vowels for itr in freq: if (isVowel(itr)): denom *= fact(freq[itr]) cnt_vwl += freq[itr] return fact(cnt_vwl) // denom # calculating no of ways to arrange the given word # such that vowels come together def all_vowels_together(freq): # calculate no of ways to arrange vowels vow = only_vowels(freq) # to store denominator of fraction denom = 1 # count of consonents cnt_cnst = 0 for itr in freq: if (isVowel(itr) == False): denom *= fact(freq[itr]) cnt_cnst += freq[itr] # calculate the number of ways to arrange # the word such that vowels come together ans = fact(cnt_cnst + 1) // denom return (ans * vow) # To calculate total number of permutations def total_permutations(freq): # To store length of the given word cnt = 0 # denominator of fraction denom = 1 for itr in freq: denom *= fact(freq[itr]) cnt += freq[itr] # return total number of permutations # of the given word return fact(cnt) // denom # Function to calculate number of permutations # such that no vowels come together def no_vowels_together(word): # to store frequency of character freq = dict() # count frequency of all characters for i in word: ch = i.lower() freq[ch] = freq.get(ch, 0) + 1 # calculate total number of permutations total = total_permutations(freq) # calculate total number of permutations # such that vowels come together vwl_tgthr = all_vowels_together(freq) # subtract vwl_tgthr from total # to get the result res = total - vwl_tgthr # return the result return res # Driver code word = "allahabad" ans = no_vowels_together(word) print(ans) word = "geeksforgeeks" ans = no_vowels_together(word) print(ans) word = "abcd" ans = no_vowels_together(word) print(ans) # This code is contributed by Mohit Kumar
C#
// C# code for above approach using System; using System.Collections.Generic; class GFG{ // Function to check if a character // is vowel or consonent static bool isVowel(char ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true; else return false; } // Function to calculate factorial of a number static long fact(long n) { if (n < 2) { return 1; } return n * fact(n - 1); } // Calculating no of ways for arranging vowels static long only_vowels(Dictionary<char, int> freq) { long denom = 1; long cnt_vwl = 0; // Iterate the map and count the number // of vowels and calculate no of ways // to arrange vowels foreach(KeyValuePair<char, int> itr in freq) { if (isVowel(itr.Key)) { denom *= fact(itr.Value); cnt_vwl += itr.Value; } } return fact(cnt_vwl) / denom; } // Calculating no of ways to arrange // the given word such that all vowels // come together static long all_vowels_together(Dictionary<char, int> freq) { // Calculate no of ways to arrange vowels long vow = only_vowels(freq); // To store denominator of fraction long denom = 1; // Count of consonents long cnt_cnst = 0; foreach(KeyValuePair<char, int> itr in freq) { if (!isVowel(itr.Key)) { denom *= fact(itr.Value); cnt_cnst += itr.Value; } } // Calculate the number of ways to // arrange the word such that // all vowels come together long ans = fact(cnt_cnst + 1) / denom; return (ans * vow); } // To calculate total number of permutations static long total_permutations(Dictionary<char, int> freq) { // To store length of the given word long cnt = 0; // Denominator of fraction long denom = 1; foreach(KeyValuePair<char, int> itr in freq) { denom *= fact(itr.Value); cnt += itr.Value; } // Return total number of // permutations of the given word return fact(cnt) / denom; } // Function to calculate number of permutations // such that no vowels come together static long no_vowels_together(string word) { // To store frequency of character Dictionary<char, int> freq = new Dictionary<char, int>(); // Count frequency of all characters for(int i = 0; i < word.Length; i++) { char ch = Char.ToLower(word[i]); if (freq.ContainsKey(ch)) { freq[ch]++; } else { freq[ch] = 1; } } // Calculate total number of permutations long total = total_permutations(freq); // Calculate total number of permutations // such that all vowels come together long vwl_tgthr = all_vowels_together(freq); // Subtract vwl_tgthr from total // to get the result long res = total - vwl_tgthr; // Return the result return res; } // Driver Code static void Main() { string word = "allahabad"; long ans = no_vowels_together(word); Console.WriteLine(ans); word = "geeksforgeeks"; ans = no_vowels_together(word); Console.WriteLine(ans); word = "abcd"; ans = no_vowels_together(word); Console.WriteLine(ans); } } // This code is contributed by divyeshrabadiya07
Javascript
<script> // Javascript code for above approach // Function to check if a character // is vowel or consonent function isVowel(ch) { if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true; else return false; } // Function to calculate factorial of a number function fact(n) { if (n < 2) { return 1; } return n * fact(n - 1); } // Calculating no of ways for arranging vowels function only_vowels(freq) { let denom = 1; let cnt_vwl = 0; // Iterate the map and count the number // of vowels and calculate no of ways // to arrange vowels for (let [key, value] of freq.entries()) { if (isVowel(key)) { denom *= fact(value); cnt_vwl += value; } } return Math.floor(fact(cnt_vwl) / denom); } // Calculating no of ways to arrange // the given word such that all vowels // come together function all_vowels_together(freq) { // Calculate no of ways to arrange vowels let vow = only_vowels(freq); // To store denominator of fraction let denom = 1; // Count of consonents let cnt_cnst = 0; for (let [key, value] of freq.entries()) { if (!isVowel(key)) { denom *= fact(value); cnt_cnst += value; } } // Calculate the number of ways to // arrange the word such that // all vowels come together let ans = Math.floor(fact(cnt_cnst + 1) / denom); return (ans * vow); } // To calculate total number of permutations function total_permutations(freq) { // To store length of the given word let cnt = 0; // Denominator of fraction let denom = 1; for (let [key, value] of freq.entries()) { denom *= fact(value); cnt += value; } // Return total number of // permutations of the given word return Math.floor(fact(cnt) / denom); } // Function to calculate number of permutations // such that no vowels come together function no_vowels_together(word) { // To store frequency of character let freq = new Map(); // Count frequency of all characters for(let i = 0; i < word.length; i++) { let ch = word[i].toLowerCase(); if (freq.has(ch)) { freq.set(ch, freq.get(ch)+1); } else { freq.set(ch, 1); } } // Calculate total number of permutations let total = total_permutations(freq); // Calculate total number of permutations // such that all vowels come together let vwl_tgthr = all_vowels_together(freq); // Subtract vwl_tgthr from total // to get the result let res = total - vwl_tgthr; // Return the result return res; } // Driver code let word = "allahabad"; let ans = no_vowels_together(word); document.write(ans+"<br>"); word = "geeksforgeeks"; ans = no_vowels_together(word); document.write(ans+"<br>"); word = "abcd"; ans = no_vowels_together(word); document.write(ans+"<br>"); // This code is contributed by unknown2108 </script>
7200 32205600 0
Complejidad del tiempo: O(n) (n = longitud de la string)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por Vivek.Pandit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA