Difficulty: Hard
I don’t like hard problems. Real.
My initial intuition for this problem is to work out the number of possible permutations given the suffix, start and finish.
I did have to look at the hints for this one (even with the hint it’s still kind of difficult - I’m bad at maths). The idea of helping a helper function to work out the number of valid permutations given the suffix from 1 to the input n. There are a few patterns that we can see based on the rules. We can split the number into 3 distinct parts: the prefix and the suffix.
There are two easy cases to handle first:
For the other cases, we first consider the prefix part of the number. We begin from the start of the prefix and iterate through the digits. If the current digit is greater than the limit, we are able to make (limit + 1) ** (length of remaining prefix including the current one) possible permutations with the rest of the digits. We can return this count early.
If the current digit is less than or equal to the limit, we consider the number of possible permutations we can make given that there is a non zero digit in our current digit location (we calculate the possible permutations with this digit as 0 later). We can make (current digit) * (limit + 1) ** (length of remaining prefix not including the current one). We then iterate to the next digit.
Lastly, we add 1 to the count if the suffix part of the number is greater than the suffix.
Then we return the valid_count(finish) - valid_count(start - 1) to get all the valid permutations between finish and start inclusive.
class Solution(object):
def numberOfPowerfulInt(self, start, finish, limit, s):
"""
:type start: int
:type finish: int
:type limit: int
:type s: str
:rtype: int
"""
def valid_count(x, s, limit):
length_x = len(x)
length_s = len(s)
if length_x < length_s:
return 0
if length_x == length_s:
return 1 if x >= s else 0
count = 0
prefix_length = length_x - length_s
for i in range(prefix_length):
# traverse through each digit
remaining_prefix = prefix_length - i - 1
if limit < int(x[i]):
count += (limit + 1) ** (remaining_prefix + 1)
return count
count += int(x[i]) * (limit + 1) ** (remaining_prefix)
if x[-length_s:] >= s:
count += 1
return count
finish_count = valid_count(str(finish), s, limit)
start_count = valid_count(str(start - 1), s, limit)
return finish_count - start_counTime Complexity:
O(log finish)Space Complexity:
O(log finish)Time Taken:
37m 51s