leetcode

commit db3649372b10388fb573d70920ee8e735c852c9f
parent 318f6f2fa77c323580e80fec30b221b1f8d253e5
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 23 Oct 2025 20:47:03 -0600

2048. next greater numerically balanced number

Diffstat:
M
balanced_num.c
 | 
43
++++++++++++++++++++++++-------------------
M
balanced_num.py
 | 
49
++++++++++++++++++++++++-------------------------

2 files changed, 48 insertions(+), 44 deletions(-)
diff --git a/balanced_num.c b/balanced_num.c
@@ -8,29 +8,34 @@
  * 'n'
  */
 
-bool is_balanced(int n) {
-  int *digit = calloc(10, sizeof(int));
-  while (n) {
-    int d = n % 10;
-    n /= 10;
-    digit[d]++;
-    if (!d || digit[d] > d)
-      return 0;
+bool is_beautiful(int *cnt) {
+  for (int i = 1; i <= 7; i++)
+    if (cnt[i] != 0 && cnt[i] != i)
+      return false;
+  return true;
+}
+
+void generate(long num, int *cnt, int *res, int *res_size) {
+  if (num > 0 && is_beautiful(cnt))
+    res[(*res_size)++] = (int)num;
+  if (num > 1224444)
+    return;
+  for (int i = 1; i <= 7; i++) {
+    if (cnt[i] < i) {
+      cnt[i]++;
+      generate(num * 10 + i, cnt, res, res_size);
+      cnt[i]--;
+    }
   }
-  for (int i = 1; i < 10; i++)
-    if (digit[i] && digit[i] != i)
-      return 0;
-  return 1;
 }
 
 int nextBeautifulNumber(int n) {
-  n += 1;
-  while (1) {
-    if (is_balanced(n))
-      return n;
-    n++;
-  }
-  return -1;
+  int res[2000], res_size = 0, cnt[10] = {0}, ans = -1;
+  generate(0, cnt, res, &res_size);
+  for (int i = 0; i < res_size; i++)
+    if (res[i] > n && (ans == -1 || res[i] < ans))
+      ans = res[i];
+  return ans;
 }
 
 int main() {
diff --git a/balanced_num.py b/balanced_num.py
@@ -1,5 +1,4 @@
 # 2048. Next Greater Numerically Balanced Number
-from collections import Counter
 
 """
 an integer 'x' is numerically balanced if for every digit 'd' in the number
@@ -10,35 +9,35 @@ an integer 'x' is numerically balanced if for every digit 'd' in the number
 
 
 class Solution(object):
+    def is_beautiful(self, cnt):
+        for i in range(1, 8):
+            if cnt[i] != 0 and cnt[i] != i:
+                return False
+        return True
+
+    def generate(self, num, cnt, nums):
+        if num > 0 and self.is_beautiful(cnt):
+            nums.append(num)
+        if num > 1224444:
+            return
+        for i in range(1, 8):
+            if cnt[i] < i:
+                cnt[i] += 1
+                self.generate(num * 10 + i, cnt, nums)
+                cnt[i] -= 1
+
     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
+        nums = []
+        self.generate(0, [0] * 10, nums)
+        nums.sort()
+        for i in nums:
+            if i > n:
+                return i
+        return -1
 
 
 if __name__ == "__main__":