aboutsummaryrefslogtreecommitdiff
path: root/balanced_num.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /balanced_num.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'balanced_num.py')
-rw-r--r--balanced_num.py48
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))