We keep dividing l by k until l is not a multiple of k any more, and then check whether l is reduced to 1 or not.
As n is limited up to 16, we can use bitmask to enumerate all the feasible combinations and check whether they can form a group or not. The total complexity is O(2n × n2).
This is a straightforward implementation problem. For each given string, we need to check the following conditions.
1) all the words end with the required suffix
2) all the words have the same gender
3) all the words appear in the required order
4) there is exactly one noun word
The idea is to previously calculate all the positions of the required prefix and suffix. Then, we enumerate every pair of feasible combination, and find out all the different substrings.
Therefore, the main task is how to determine whether two strings are the same or not. I did not come up with a good solution, however I studied the other accepted codes.
I found that they adopt an “unsigned long long int” variable x, initialized with zero value, and compute x = x × prime + s[i], where prime is a prime integer. I think this means to transform or map the string to an integer, like hash table. However, I did not figure out how could this guarantee that no two strings are mapped to the same integer, since we have at most 262000 different strings but only 264 integers. Although for some substring of length m, we can in fact only have O(n) different ones, which is quite small compared with 264, but this still can not guarantee that no collisions occur...
There is a standard solution, referred to as “sieve function”, to this problem. Using “bitset” can also solve the memory problem. Instead of testing each prime integer, we can enumerate a and b, and then test whether the result of a2 + b2 is prime or not. The complexity is O(ab) = O(n). To further decrease the constant of complexity, for each value of a, we can start enumerating the value of b from a + 1, with increment step of 2. The reason is that if both a and b are even or odd, the value of a2 + b2 must be an even integer, and thus is definitely not a prime integer.
Комментарии (0)
