Problem

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 _thesmallest numerically balanced number strictly greater than _n .

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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 <= 10^6

Solution

Method 1 -

Intuition

Numerically balanced numbers are rare and have a specific digit frequency pattern. Since n ≤ 10^6, we can enumerate all possible candidates up to a reasonable upper bound and pick the smallest one greater than n.

Approach

Generate all numbers up to a certain limit (e.g., 1224444) and check if each is numerically balanced. For each number, count the frequency of each digit and verify that for every digit d > 0, the count of d is exactly d, and no digit 0 appears. Return the smallest such number greater than n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

bool isBalanced(int x) {
    int cnt[10] = {};
    int y = x;
    while (y) { cnt[y%10]++; y /= 10; }
    for (int d = 1; d < 10; ++d) {
        if (cnt[d] && cnt[d] != d) return false;
    }
    return cnt[0] == 0;
}
int nextBalanced(int n) {
    for (int x = n+1; x <= 1224444; ++x) {
        if (isBalanced(x)) return x;
    }
    return -1;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func isBalanced(x int) bool {
    cnt := [10]int{}
    y := x
    for y > 0 {
        cnt[y%10]++
        y /= 10
    }
    for d := 1; d < 10; d++ {
        if cnt[d] > 0 && cnt[d] != d { return false }
    }
    return cnt[0] == 0
}
func nextBalanced(n int) int {
    for x := n+1; x <= 1224444; x++ {
        if isBalanced(x) { return x }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int nextBalanced(int n) {
    for (int x = n+1; x <= 1224444; x++) {
        if (isBalanced(x)) return x;
    }
    return -1;
}
private boolean isBalanced(int x) {
    int[] cnt = new int[10];
    int y = x;
    while (y > 0) { cnt[y%10]++; y /= 10; }
    for (int d = 1; d < 10; d++) {
        if (cnt[d] > 0 && cnt[d] != d) return false;
    }
    return cnt[0] == 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fun nextBalanced(n: Int): Int {
    for (x in n+1..1224444) {
        if (isBalanced(x)) return x
    }
    return -1
}
fun isBalanced(x: Int): Boolean {
    val cnt = IntArray(10)
    var y = x
    while (y > 0) {
        cnt[y%10]++
        y /= 10
    }
    for (d in 1..9) {
        if (cnt[d] > 0 && cnt[d] != d) return false
    }
    return cnt[0] == 0
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def is_balanced(x: int) -> bool:
    cnt = [0]*10
    y = x
    while y:
        cnt[y%10] += 1
        y //= 10
    for d in range(1, 10):
        if cnt[d] and cnt[d] != d:
            return False
    return cnt[0] == 0

def next_balanced(n: int) -> int:
    for x in range(n+1, 1224445):
        if is_balanced(x):
            return x
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fn is_balanced(x: i32) -> bool {
    let mut cnt = [0; 10];
    let mut y = x;
    while y > 0 {
        cnt[(y%10) as usize] += 1;
        y /= 10;
    }
    for d in 1..10 {
        if cnt[d] > 0 && cnt[d] != d as i32 { return false; }
    }
    cnt[0] == 0
}
fn next_balanced(n: i32) -> i32 {
    for x in n+1..=1224444 {
        if is_balanced(x) { return x; }
    }
    -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

function isBalanced(x: number): boolean {
    const cnt = Array(10).fill(0);
    let y = x;
    while (y > 0) {
        cnt[y%10]++;
        y = Math.floor(y/10);
    }
    for (let d = 1; d < 10; d++) {
        if (cnt[d] > 0 && cnt[d] !== d) return false;
    }
    return cnt[0] === 0;
}
function nextBalanced(n: number): number {
    for (let x = n+1; x <= 1224444; x++) {
        if (isBalanced(x)) return x;
    }
    return -1;
}

Complexity

  • ⏰ Time complexity: O(K * D) where K is the number of candidates checked (worst-case ~1e6), D is number of digits (≤7).
  • 🧺 Space complexity: O(1).