diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /balanced_num.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'balanced_num.py')
-rw-r--r-- | balanced_num.py | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/balanced_num.py b/balanced_num.py new file mode 100644 index 0000000..b9ed677 --- /dev/null +++ b/balanced_num.py @@ -0,0 +1,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)) |