PROBLEM LINKS:Author: sikander_nsit DIFFICULTY:EASYMEDIUM PROBLEM:Given string S and number L we had to find the number of valid passwords. There are three conditions on the password.
EXPLANATION:Let us take an example to understand it. Given string is: “DBF” and L=6. Strings with maximum length 1 which are smaller than “DBF” are “A”, “B”, “C” and “D” so 4. The first part of the answer can be calculated in O(n) where n is length of given string using the following pseudocode.
The second part can be calculated using the formula for the sum of GP. Since L can be very large modular exponentiation can be used to do this in O(log L). Also the term 25 in the denominator while calculating the GP sum would have to be taken care of. For this inverse modulus can be used also logarithmic time. AUTHOR'S SOLUTION:Author's solution can be found here.
This question is marked "community wiki".
asked 11 Feb '14, 03:54
