Last Updated: 7 Jan, 2021
Count Valid Pairs
Moderate
Asked in company
Ninja has been learning about strings recently. While studying, he was fascinated by a pair of strings, say P and Q, in which every character in the first string, P, is less than the corresponding character in the second string, Q, i.e. P[i] < Q[i], where 0 <= 'i' < Length.
Now, he wants to count the number of such pairs of strings, of length 'N', which satisfies this rule.
Note:
1. Strings contain only lower-case English alphabets.
2. Since the number of such pairs can be very large, return the answer modulo 10^9 + 7.
Example:
Let’s say length 'N' = 1. So, we’ll consider only the strings with length 1: “a”, “b”, “c”, ….., “z”. Now, If P = “a”, then Q can be “b”, “c”, “d”....., “z” (25 possibilities). If P = “b”, then Q can be “c”, “d”....., “z” (24 possibilities). And so on till P = “y”, then Q can be “z” (1 possibility).
Hence, the total number of pairs of strings that satisfy the given condition is: 25 + 24 + …… + 1 = 325.
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases.
The first and the only line of every test case contains an integer ‘N’ representing the length of the pairs of strings to be found.
Output Format:
For each test case, return the number of pairs of strings that satisfy the given condition.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10^8
Where ‘N’ is the length of the pairs of strings to be found.
Time limit: 1 sec
Approaches
A brute force approach could be to generate all the possible strings of length N and for each string, say P, we count the number of possible strings Q which satisfy the given condition. The idea is to start with an empty string and recursively append the characters to the string until we get a string of length 'N'. After generating a string, we iterate over it. For any character 'ch' present at index ‘i’ in the string ‘P’ (i.e. the generated string) ‘Q[i]' can store all the characters greater than ‘ch’ (using the given condition) i.e. 'COUNT' = ‘z’ - 'ch'.
Multiplying the count value for every index, gives us the number of possible strings Q, for the generated string, 'P'.
Now, repeat the above procedure for the rest of the strings. The sum of all the count of possible strings Q, for all the generated strings, gives us the final answer.
The idea here is to identify the pattern in the number of possible pairs of strings for different lengths. From the example, we understood that for the strings of length 1, the number of pairs of strings that satisfy the given condition is 325.
In order to identify the pattern let’s understand another example for strings of length 2. The possible strings of length 2 are: “aa”, “ab”,......, “az”, “ba”, “bb”, ……, “bz”,....., “zz”. Consider string “aa” as P. Now, we find the number of possible strings Q, which satisfy the given condition (i.e. every character in P, should be less than the corresponding character in Q).
The possible values of Q are - “bb”, “bc”,....., “bz”, “cb”, and so on till “zz”, giving us a total of 25 * 25 possible strings. Observing the above pattern we calculate the number of possible values of Q for the strings “aa”, “ab”, …..,“az” and add them, this gives us:
- 25*25 + 25*24 + 25*23 ….. + 25*1
- i.e. 25 * (25 + 24 + 23 +....... + 1)
- i.e. 25 * 325.
- Similarly, for the strings “ba”, “bb” and so on till “bz”, we get:
- 24*25 + 24*24 + 24*23 ….. + 24*1
- i.e. 24 * (25 + 24 + 23 +....... + 1)
- i.e. 24 * 325
- Repeating the same procedure for the remaining strings and adding all results, we get:
- 25 * 325 + 24 * 325 + 23 * 325 + ……. + 1 * 325
- i.e. 325 * (25 + 24 + 23 + ….. 1)
- i.e. 325 * 325 = 325^2.
- This is the same as 365^L, where L = 2.
Hence, we can generalize this for strings of length L. So, the problem transforms into calculating (325^L) MOD 1000000007. In order to do so, we run a loop from 1 to L to calculate 365^L and take modulo at each iteration.
Instead of multiplying 325 ‘N’ times. A better approach is to use the concept of binary exponentiation. Binary exponentiation (or exponentiation by squaring) allows us to calculate a ^ 'N' using only O(log('N')) multiplications instead of ‘N’ multiplications.
The idea is to split a ^ 'N' using the binary representation of ‘N’.
For example, let a = 5 and ‘N’ = 11.
- 11 in binary representation can be written as 1011.
- Therefore, 5^11 can be represented as 5^(1011 Base 2) i.e. 5 ^ (1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0) = 5 ^ (8 + 2 + 1).
- Hence, 5^11 = 5^8 + 5^2 + 5^1.
Here, ‘N’ will always have a maximum of (FLOOR(Log'N' base 2) + 1) digits in its binary representation. Hence, if we can calculate each of the powers of a in O(1) time (single multiplication operation) we will only require O(log('N')) multiplications to calculate a ^ 'N'.
If we observe carefully we can see that the next value is the square of the previous one, hence we can easily calculate the next value by squaring the previous one.
- i.e. 5^1 = 5
- 5^2 = (5^1)^2 = 5^2 = 25
- 5^4 = (5^2)^2 = 5^4 = 625
- 5^8 = (5^4)^2 = 5^8 = 390625.
To obtain the answer we add only those values whose exponents are present in the binary representation of 'N'.