# 2048. Next Greater Numerically Balanced Number

## 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^6]$, and one of the balanced numbers greater than $10^6$ is $1224444$. Therefore, we directly enumerate $x \in [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)$.

• 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;
}
}
}
}

• 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;
}
}
}
};

• 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


• 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
}
}
}

• 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;
}
}
}