aboutsummaryrefslogtreecommitdiff
path: root/count_number_powerful_integers.py
blob: da7794054c76ca4ee54559478e03559201bbd09f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 2999. Count the Number of Powerful Integers

"""
you are given three integers 'start', 'finish', and 'limit'. you are also
given a 0-indexed string 's' representing a positive integer. a positive
integer 'x' is called powerful if it ends with 's' and each digit in 'x' is
at most 'limit'. return the total number of powerful integers in the range
'[start .. finish]'. a string 'x' is a suffix of a string 'y' if and only if
'x' is a substring of 'y' that starts from some index in 'y' and extends to
the index 'y.length - 1'.
"""


class Solution(object):
    def numberOfPowerfulInt(self, start, finish, limit, s):
        """
        :type start: int
        :type finish: int
        :type limit: int
        :type s: str
        :rtype: int
        """
        cnt = [0] * 16

        def get_cnt(n, s):
            res, i, size = cnt[len(n) - 1], 0, len(n) - len(s)
            while True:
                res += (
                    n[i:] >= s
                    if i == size
                    else cnt[len(n) - i - 1] * (min(limit, int(n[i]) - 1) + (i > 0))
                )
                i += 1
                if i > size or int(n[i - 1]) > limit:
                    break
            return res

        for i in range(len(s), 16):
            cnt[i] = 1 if i == len(s) else cnt[i - 1] * (limit + 1)
        return get_cnt(str(finish), s) - get_cnt(str(start - 1), s)


if __name__ == "__main__":
    obj = Solution()
    print(obj.numberOfPowerfulInt(start=1, finish=6000, limit=4, s="124"))
    print(obj.numberOfPowerfulInt(start=15, finish=215, limit=6, s="10"))
    print(obj.numberOfPowerfulInt(start=1000, finish=2000, limit=4, s="3000"))