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
16
17
18
19

class Solution {
private:
    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;
    }
public:
    int nextBeautifulNumber(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 nextBeautifulNumber(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
16
17

class Solution {
    public int nextBeautifulNumber(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
19
20

class Solution {
    private 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
    }
    fun nextBeautifulNumber(n: Int): Int {
        for (x in n+1..1224444) {
            if (isBalanced(x)) return x
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        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
        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
19
20

impl Solution {
    pub fn next_beautiful_number(n: i32) -> i32 {
        for x in n+1..=1224444 {
            if Self::is_balanced(x) { return x; }
        }
        -1
    }
    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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    private 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;
    }
    nextBeautifulNumber(n: number): number {
        for (let x = n+1; x <= 1224444; x++) {
            if (this.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).