Given an English word of length at most 20 characters. Calculate the number of ways to arrange the word such that no vowels occur together.
Note: If the total number of vowels in the given word is one then the result should be 0.
Examples:
Input : Allahabad
Output : 7200Input : neveropen
Output : 32205600Input : abcd
Output : 0
Since the word contains vowels and consonants. Calculate the total number of ways to arrange the given word and subtract the number of ways having all vowels together. To calculate the total number of ways we’ll use the following formula-
No of ways = (n!) / (r1! * r2! * ... * rk!)
Where n is the number of different characters in the word and r1, r2 … rk, are the frequency of same type character.
In order to calculate the number of ways such that all vowels occur together, we consider the group of all vowels as a single character and using the above formula we’ll calculate the total number of ways having all vowel together. Now subtract it from the total number of ways to get the result.
Below is the implementation of the above approach:
C++
// C++ code for above approach #include <bits/stdc++.h>#define ll long long intusing namespace std;// Function to check if a character is vowel or consonantbool 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 numberll fact(ll n){ if (n < 2) return 1; return n * fact(n - 1);}// Calculating no of ways for arranging vowelsll 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 togetherll 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 consonants 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 permutationsll 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 togetherll 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 codeint main(){ string word = "allahabad"; ll ans = no_vowels_together(word); cout << ans << endl; word = "neveropen"; 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 consonant 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 consonants 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 = "neveropen"; 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 consonantdef 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 numberdef fact(n): if (n < 2): return 1 return n * fact(n - 1)# Calculating no of ways for arranging vowelsdef 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 togetherdef all_vowels_together(freq): # calculate no of ways to arrange vowels vow = only_vowels(freq) # to store denominator of fraction denom = 1 # count of consonants 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 permutationsdef 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 togetherdef 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 codeword = "allahabad"ans = no_vowels_together(word)print(ans)word = "neveropen"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 consonant 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 consonants 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 Codestatic void Main() { string word = "allahabad"; long ans = no_vowels_together(word); Console.WriteLine(ans); word = "neveropen"; 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 consonantfunction isVowel(ch){ if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') return true; else return false;} // Function to calculate factorial of a numberfunction fact(n){ if (n < 2) { return 1; } return n * fact(n - 1);}// Calculating no of ways for arranging vowelsfunction 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 togetherfunction 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 consonants 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 permutationsfunction 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 togetherfunction 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 codelet word = "allahabad"; let ans = no_vowels_together(word); document.write(ans+"<br>"); word = "neveropen"; 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> |
Output:
7200 32205600 0
Time Complexity : O(n) (n = length of string)
Auxiliary Space: O(n), space required for the recursive stack space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
