Next Greater Numerically Balanced Number

medium enumeration digit counting hash table

Problem

An integer x is numerically balanced if, for every digit d that appears in x, the digit d occurs exactly d times. Given an integer n, return the smallest numerically balanced number strictly greater than n.

Inputn = 1

Output22

22 is balanced: the digit 2 occurs exactly 2 times. It is the smallest balanced number above 1.

Inputn = 1000

Output1333

1 occurs 1 time and 3 occurs 3 times. Note 1022 fails because 0 appears though 0 must occur 0 times.

n (non-negative integer)

def next_balanced(n):
    cand = n + 1
    while True:
        count = [0] * 10
        for ch in str(cand):
            count[int(ch)] += 1
        balanced = True
        for d in range(10):
            if count[d] != 0 and count[d] != d:
                balanced = False
                break
        if balanced:
            return cand
        cand += 1

function nextBalanced(n) {
  let cand = n + 1;
  while (true) {
    const count = new Array(10).fill(0);
    for (const ch of String(cand)) {
      count[Number(ch)]++;
    }
    let balanced = true;
    for (let d = 0; d < 10; d++) {
      if (count[d] !== 0 && count[d] !== d) {
        balanced = false;
        break;
      }
    }
    if (balanced) return cand;
    cand++;
  }
}

int nextBalanced(int n) {
    int cand = n + 1;
    while (true) {
        int[] count = new int[10];
        for (char ch : String.valueOf(cand).toCharArray()) {
            count[ch - '0']++;
        }
        boolean balanced = true;
        for (int d = 0; d < 10; d++) {
            if (count[d] != 0 && count[d] != d) {
                balanced = false;
                break;
            }
        }
        if (balanced) return cand;
        cand++;
    }
}

int nextBalanced(int n) {
    int cand = n + 1;
    while (true) {
        int count[10] = {0};
        for (char ch : to_string(cand)) {
            count[ch - '0']++;
        }
        bool balanced = true;
        for (int d = 0; d < 10; d++) {
            if (count[d] != 0 && count[d] != d) {
                balanced = false;
                break;
            }
        }
        if (balanced) return cand;
        cand++;
    }
}

Explanation

The answer is tightly bounded: for any n ≤ 10⁶, the smallest balanced number above it is at most 1224444 (1 once, 2 twice, 4 four times). So a clean and reliable strategy is to scan candidates upward from n + 1 and return the first one that is balanced.

Testing one candidate is a simple digit-count check. We build a frequency table count[0..9] by walking the candidate's digits, then verify the balance rule: for every digit d, its count is either 0 (the digit is absent) or exactly d (it appears the required number of times). Any digit whose count is non-zero but not equal to itself breaks the rule.

The digit 0 is handled automatically: 0 must occur 0 times, so the moment a 0 appears its count becomes non-zero while the requirement stays 0, and the candidate is rejected.

As soon as a candidate passes the check, it is by construction the smallest balanced value strictly greater than n, because we examined every integer in between and rejected each one.

Example: starting from n = 15 we test 16, 17, 18, 19 (each has a lone large digit), 20 and 21 (an unbalanced digit), and finally 22, where the digit 2 appears exactly twice — the answer.

Time: O(R · L) Space: O(1)