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>
Producción:
176400
Complejidad temporal: O(2 n )
Espacio auxiliar: O(n)