Dada una palabra que contiene vocales y consonantes. La tarea es encontrar de cuántas maneras se pueden organizar las palabras para que las vocales siempre estén juntas. Dado que la longitud de la palabra <10.
Ejemplos:
Input: str = "geek" Output: 6 Ways such that both 'e' comes together are 6 i.e. geek, gkee, kgee, eekg, eegk, keeg Input: str = "corporation" Output: 50400
Planteamiento: Dado que la palabra contiene vocales y consonantes juntas. Se necesitan todas las vocales para permanecer juntas, entonces tomaremos todas las vocales como una sola letra.
Como en la palabra ‘geeksforgeeks’, podemos tratar las vocales «eeoee» como una sola letra.
Por lo tanto, tenemos gksfrgks (eeoee) .
Este tiene 9 (8 + 1) letras de las cuales g, k, s cada una ocurre 2 veces y el resto son diferentes.
El número de formas en que se organizan estas letras = 9!/(2!)x(2!)x(2!) = 45360 formas
Ahora, 5 vocales en las que ‘e’ aparece 4 veces y ‘o’ aparece 1 vez, pueden ser arreglado en 5! /4! = 5 maneras.
Número requerido de vías = (45360 x 5) = 226800
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to calculate the no. of ways
// to arrange the word having vowels together
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Factorial of a number
ll fact(int n)
{
ll f = 1;
for (int i = 2; i <= n; i++)
f = f * i;
return f;
}
// calculating ways for arranging consonants
ll waysOfConsonants(int size1, int freq[])
{
ll ans = fact(size1);
for (int i = 0; i < 26; i++) {
// Ignore vowels
if (i == 0 || i == 4 || i == 8 || i == 14 || i == 20)
continue;
else
ans = ans / fact(freq[i]);
}
return ans;
}
// calculating ways for arranging vowels
ll waysOfVowels(int size2, int freq[])
{
return fact(size2) / (fact(freq[0]) * fact(freq[4]) * fact(freq[8])
* fact(freq[14]) * fact(freq[20]));
}
// Function to count total no. of ways
ll countWays(string str)
{
int freq[26] = { 0 };
for (int i = 0; i < str.length(); i++)
freq[str[i] - 'a']++;
// Count vowels and consonant
int vowel = 0, consonant = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] != 'a' && str[i] != 'e' && str[i] != 'i'
&& str[i] != 'o' && str[i] != 'u')
consonant++;
else
vowel++;
}
// total no. of ways
return waysOfConsonants(consonant+1, freq) *
waysOfVowels(vowel, freq);
}
// Driver code
int main()
{
string str = "geeksforgeeks";
cout << countWays(str) << endl;
return 0;
}
Java
// Java program to calculate the no. of
// ways to arrange the word having
// vowels together
import java.util.*;
class GFG{
// Factorial of a number
static int fact(int n)
{
int f = 1;
for(int i = 2; i <= n; i++)
f = f * i;
return f;
}
// Calculating ways for arranging consonants
static int waysOfConsonants(int size1,
int []freq)
{
int ans = fact(size1);
for(int i = 0; i < 26; i++)
{
// Ignore vowels
if (i == 0 || i == 4 || i == 8 ||
i == 14 || i == 20)
continue;
else
ans = ans / fact(freq[i]);
}
return ans;
}
// Calculating ways for arranging vowels
static int waysOfVowels(int size2, int [] freq)
{
return fact(size2) / (fact(freq[0]) *
fact(freq[4]) * fact(freq[8]) *
fact(freq[14]) * fact(freq[20]));
}
// Function to count total no. of ways
static int countWays(String str)
{
int []freq = new int [200];
for(int i = 0; i < 200; i++)
freq[i] = 0;
for(int i = 0; i < str.length(); i++)
freq[str.charAt(i) - 'a']++;
// Count vowels and consonant
int vowel = 0, consonant = 0;
for(int i = 0; i < str.length(); i++)
{
if (str.charAt(i) != 'a' && str.charAt(i) != 'e' &&
str.charAt(i) != 'i' && str.charAt(i) != 'o' &&
str.charAt(i) != 'u')
consonant++;
else
vowel++;
}
// Total no. of ways
return waysOfConsonants(consonant + 1, freq) *
waysOfVowels(vowel, freq);
}
// Driver code
public static void main(String []args)
{
String str = "geeksforgeeks";
System.out.println(countWays(str));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to calculate
# the no. of ways to arrange
# the word having vowels together
# Factorial of a number
def fact(n):
f = 1
for i in range(2, n + 1):
f = f * i
return f
# calculating ways for
# arranging consonants
def waysOfConsonants(size1, freq):
ans = fact(size1)
for i in range(26):
# Ignore vowels
if (i == 0 or i == 4 or
i == 8 or i == 14 or
i == 20):
continue
else:
ans = ans // fact(freq[i])
return ans
# calculating ways for
# arranging vowels
def waysOfVowels(size2, freq):
return (fact(size2) // (fact(freq[0]) *
fact(freq[4]) * fact(freq[8]) *
fact(freq[14]) * fact(freq[20])))
# Function to count total no. of ways
def countWays(str1):
freq = [0] * 26
for i in range(len(str1)):
freq[ord(str1[i]) -
ord('a')] += 1
# Count vowels and consonant
vowel = 0
consonant = 0
for i in range(len(str1)):
if (str1[i] != 'a' and str1[i] != 'e' and
str1[i] != 'i' and str1[i] != 'o' and
str1[i] != 'u'):
consonant += 1
else:
vowel += 1
# total no. of ways
return (waysOfConsonants(consonant + 1, freq) *
waysOfVowels(vowel, freq))
# Driver code
if __name__ == "__main__":
str1 = "geeksforgeeks"
print(countWays(str1))
# This code is contributed by Chitranayal
C#
// C# program to calculate the no. of
// ways to arrange the word having
// vowels together
using System.Collections.Generic;
using System;
class GFG{
// Factorial of a number
static int fact(int n)
{
int f = 1;
for(int i = 2; i <= n; i++)
f = f * i;
return f;
}
// Calculating ways for arranging consonants
static int waysOfConsonants(int size1,
int []freq)
{
int ans = fact(size1);
for(int i = 0; i < 26; i++)
{
// Ignore vowels
if (i == 0 || i == 4 || i == 8 ||
i == 14 || i == 20)
continue;
else
ans = ans / fact(freq[i]);
}
return ans;
}
// Calculating ways for arranging vowels
static int waysOfVowels(int size2, int [] freq)
{
return fact(size2) / (fact(freq[0]) *
fact(freq[4]) * fact(freq[8]) *
fact(freq[14]) * fact(freq[20]));
}
// Function to count total no. of ways
static int countWays(string str)
{
int []freq = new int [200];
for(int i = 0; i < 200; i++)
freq[i] = 0;
for(int i = 0; i < str.Length; i++)
freq[str[i] - 'a']++;
// Count vowels and consonant
int vowel = 0, consonant = 0;
for(int i = 0; i < str.Length; i++)
{
if (str[i] != 'a' && str[i] != 'e' &&
str[i] != 'i' && str[i] != 'o' &&
str[i] != 'u')
consonant++;
else
vowel++;
}
// Total no. of ways
return waysOfConsonants(consonant + 1, freq) *
waysOfVowels(vowel, freq);
}
// Driver code
public static void Main()
{
string str = "geeksforgeeks";
Console.WriteLine(countWays(str));
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript program to calculate the no. of
// ways to arrange the word having
// vowels together
// Factorial of a number
function fact(n)
{
let f = 1;
for(let i = 2; i <= n; i++)
f = f * i;
return f;
}
// Calculating ways for arranging consonants
function waysOfConsonants(size1,freq)
{
let ans = fact(size1);
for(let i = 0; i < 26; i++)
{
// Ignore vowels
if (i == 0 || i == 4 || i == 8 ||
i == 14 || i == 20)
continue;
else
ans = Math.floor(ans / fact(freq[i]));
}
return ans;
}
// Calculating ways for arranging vowels
function waysOfVowels(size2,freq)
{
return Math.floor(fact(size2) / (fact(freq[0]) *
fact(freq[4]) * fact(freq[8]) *
fact(freq[14]) * fact(freq[20])));
}
// Function to count total no. of ways
function countWays(str)
{
let freq = new Array(200);
for(let i = 0; i < 200; i++)
freq[i] = 0;
for(let i = 0; i < str.length; i++)
freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// Count vowels and consonant
let vowel = 0, consonant = 0;
for(let i = 0; i < str.length; i++)
{
if (str[i] != 'a' && str[i] != 'e' &&
str[i] != 'i' && str[i] != 'o' &&
str[i] != 'u')
consonant++;
else
vowel++;
}
// Total no. of ways
return waysOfConsonants(consonant + 1, freq) *
waysOfVowels(vowel, freq);
}
// Driver code
let str = "geeksforgeeks";
document.write(countWays(str));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
226800
Optimizaciones adicionales: podemos precalcular los valores factoriales requeridos para evitar nuevos cálculos.
Publicación traducida automáticamente
Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA