PROBLEM LINK:
Author: Ashish Ahuja
Tester: Ashish Ahuja
Editorialist: Ashish Ahuja
DIFFICULTY:
MEDIUM
PREREQUISITES:
String processing, Permutations & Combinations
PROBLEM:
The problem is based on the dictionary position of words formed randomly from the given string of letters.
QUICK EXPLANATION:
The programmer is required to place a letter out of the given letters, at the start of the string, and then find out dictionary position of the first and the last word formed with that letter at the beginning.
EXPLANATION:
Here, the only catch is to find out the dictionary position after successfully placing a letter at the start of the string.
For instance, if 5 random letters are given -
t z k i o
Then the solution demands that you place one of the letters at the index ‘0’ of the string. Let us take -
o
Now with, ‘o’ at the start there are 4! ways to place the rest of the letters.
We have to find out the first and the last way of these 4! ways, i.e. the first and the last word formed from these 5 letters with ‘o’ at the beginning of the string.
A small code snippet is as follows -
int fact(int n)
{
if(n==1)
return(1);
else
return(n*fact(n-1));
}
This function is used to find the number of ways to place the letters of the string with the position of the first letter fixed. Then, we use this function to give us the position of the first and the last words in the dictionary, which start and end with the specified letter.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.