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
48
|
# 2048. Next Greater Numerically Balanced Number
from collections import Counter
"""
an integer 'x' is numerically balanced if for every digit 'd' in the number
'x', there are exactly 'd' occurences of that digit in 'x'. given an integer
'n', return the smallest numerically balanced number strictly greater than
'n'
"""
class Solution(object):
def nextBeautifulNumber(self, n):
"""
:type n: int
:rtype: int
"""
def backtracking(i, numLen, curNum, counter):
if i == numLen:
isBalanceNumber = True
for d, freq in counter.items():
if freq != 0 and d != freq:
isBalanceNumber = False
if isBalanceNumber:
yield curNum
return
for d in range(1, numLen + 1):
if counter[d] >= d:
continue
if counter[d] + (numLen - i) < d:
continue
counter[d] += 1
yield from backtracking(i + 1, numLen, curNum * 10 + d, counter)
counter[d] -= 1
for numLen in range(len(str(n)), len(str(n)) + 2):
for num in backtracking(0, numLen, 0, Counter()):
if num > n:
return num
if __name__ == "__main__":
obj = Solution()
print(obj.nextBeautifulNumber(1))
print(obj.nextBeautifulNumber(1000))
print(obj.nextBeautifulNumber(3000))
|