PROBLEM LINK:
Mansi and Her Student
Author: Mansi Khara
Tester: Dipen Ved
Editorialist: Mansi Khara
Under KJSCE CODECELL
DIFFICULTY:
EASY
PREREQUISITES:
Math Combination and Factorial concepts.
PROBLEM:
The problem is to find out the number of words which can be made using P consonants and Q vowels from an original word, where P and Q are less than the number of consonants and vowels in the original word respectively.
QUICK EXPLANATION:
P consonants are chosen from the original number of consonants using combination function and Q consonants are chosen from the original number using combination. The letter chosen are arranged in themselves using the factorial function.
EXPLANATION:
The problem is to choose given number of consonants and vowels from the word given and make a word. The number of words possible is to be displayed as the output. Here we use the combination function that chooses P consonants(P given) from the original word.
The following is the Combination function:
long long int binomialCoeff(long long int n,long long int k)
{
if (k==0 || k==n)
return 1;
return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
After choosing P and Q consonants, we multiply the answers to generate the number of possible words using them.
Next, we also add the factorial function to consider the possibility of the arranging the letters among themselves.
The factorial of P+Q is considered as the total number of letters in the final word has to be P+Q.
The following is the factorial function:
long long int multiplyNumbers(long long int n)
{
if (n >= 1)
return n*multiplyNumbers(n-1);
else
return 1;
}
The answer to the factorial function is again multiplied to the result of both the combination functions.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solution can be found here.