LeetCode 2048. Next Greater Numerically Balanced Number Solution in Java, C++, Python & More | Explanation + Code

Description

An integer x is numerically balanced if for every digit d in the number x, there are exactly d occurrences of that digit in x.

Given an integer n, return the smallest numerically balanced number strictly greater than n.

 

Example 1:

Input: n = 1
Output: 22
Explanation: 
22 is numerically balanced since:
- The digit 2 occurs 2 times. 
It is also the smallest numerically balanced number strictly greater than 1.

Example 2:

Input: n = 1000
Output: 1333
Explanation: 
1333 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times. 
It is also the smallest numerically balanced number strictly greater than 1000.
Note that 1022 cannot be the answer because 0 appeared more than 0 times.

Example 3:

Input: n = 3000
Output: 3133
Explanation: 
3133 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times.
It is also the smallest numerically balanced number strictly greater than 3000.

 

Constraints:

• 0 <= n <= 106

Solutions

Solution 1: Enumeration

We note that the range of n in the problem is [0, 10⁶], and one of the balanced numbers greater than 10⁶ is 1224444. Therefore, we directly enumerate x ∈ [n + 1, ..] and then judge whether x is a balanced number. The enumerated x will definitely not exceed 1224444.

The time complexity is O(M - n), where M = 1224444. The space complexity is O(1).

PythonJavaC++GoTypeScriptRust

class Solution: def nextBeautifulNumber(self, n: int) -> int: for x in count(n + 1): y = x cnt = [0] * 10 while y: y, v = divmod(y, 10) cnt[v] += 1 if all(v == 0 or i == v for i, v in enumerate(cnt)): return x(code-box)

class Solution { public int nextBeautifulNumber(int n) { for (int x = n + 1;; ++x) { int[] cnt = new int[10]; for (int y = x; y > 0; y /= 10) { ++cnt[y % 10]; } boolean ok = true; for (int y = x; y > 0; y /= 10) { if (y % 10 != cnt[y % 10]) { ok = false; break; } } if (ok) { return x; } } } }(code-box)

class Solution { public: int nextBeautifulNumber(int n) { for (int x = n + 1;; ++x) { int cnt[10]{}; for (int y = x; y > 0; y /= 10) { ++cnt[y % 10]; } bool ok = true; for (int y = x; y > 0; y /= 10) { if (y % 10 != cnt[y % 10]) { ok = false; break; } } if (ok) { return x; } } } };(code-box)

func nextBeautifulNumber(n int) int { for x := n + 1; ; x++ { cnt := [10]int{} for y := x; y > 0; y /= 10 { cnt[y%10]++ } ok := true for y := x; y > 0; y /= 10 { if y%10 != cnt[y%10] { ok = false break } } if ok { return x } } }(code-box)

function nextBeautifulNumber(n: number): number { for (let x = n + 1; ; ++x) { const cnt: number[] = Array(10).fill(0); for (let y = x; y > 0; y = (y / 10) | 0) { cnt[y % 10]++; } let ok = true; for (let i = 0; i < 10; ++i) { if (cnt[i] && cnt[i] !== i) { ok = false; break; } } if (ok) { return x; } } }(code-box)

impl Solution { pub fn next_beautiful_number(n: i32) -> i32 { let mut x = n + 1; loop { let mut cnt = [0; 10]; let mut y = x; while y > 0 { cnt[(y % 10) as usize] += 1; y /= 10; } let mut ok = true; let mut y2 = x; while y2 > 0 { let d = (y2 % 10) as usize; if d != cnt[d] { ok = false; break; } y2 /= 10; } if ok { return x; } x += 1; } } }(code-box)