2048. Next Greater Numerically Balanced Number Solution

The 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 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 <= 10⁶

Approach overview

Problem Overview: Given an integer n, return the smallest integer strictly greater than n where every digit appears exactly as many times as its value. For example, 22 is numerically balanced because digit 2 appears twice, while 1333 is balanced because digit 1 appears once and digit 3 appears three times.

Approach 1: Brute Force Search (Time: O(k * d), Space: O(1))

Start from n + 1 and increment one number at a time. For each candidate, count digit frequencies using a small array of size 10. A number is numerically balanced if every digit d appears exactly d times and digits with frequency > 0 satisfy the rule. Each validation scans the digits of the number, which takes O(d) where d is the number of digits. Since the search space is small (balanced numbers are rare and typically below 10⁷), this brute force approach performs surprisingly well in practice. This method mainly relies on simple counting logic from math and is easy to implement during interviews.

Approach 2: Permutations with Digit Limits (Time: O(P), Space: O(P))

Instead of scanning every number, generate only valid numerically balanced numbers. The key observation: a balanced number can only contain digits 1–9 where the count of each digit equals the digit itself. That means valid digit sets look like {1}, {2,2}, {1,2,2}, {3,3,3}, etc. Build candidate digit multisets where the frequency rule already holds, then generate all permutations of those digits. Convert each permutation to an integer and keep only those greater than n. Finally return the minimum valid candidate. Generation can be implemented using backtracking or direct enumeration. Because the total number of balanced numbers is tiny, this approach efficiently precomputes all possibilities and performs a simple comparison search.

Recommended for interviews: Start with brute force to show you understand the definition and validation logic. Then explain the enumeration insight: balanced numbers have strict digit-frequency constraints, so generating valid permutations dramatically reduces the search space. Interviewers usually expect you to recognize this constraint-based enumeration since it avoids unnecessary checks and demonstrates stronger algorithmic reasoning.

Approach 1: Brute Force Search

This method involves incrementing the number starting from n+1 and checking each number to see if it is numerically balanced. This approach is straightforward but not optimal as it checks each number one by one.

Python

def is_balanced(x):
    from collections import Counter
    s = str(x)
    count = Counter(s)
    return all(count[d] == int(d) for d in count if '0' < d <= '9')

def next_balanced(n):
    current = n + 1
    while True:
        if is_balanced(current):
            return current
        current += 1

print(next_balanced(1))  # Output: 22

Java

import java.util.Arrays;

public class NextBalanced {
    public static boolean isBalanced(int x) {
        char[] digits = String.valueOf(x).toCharArray();
        int[] count = new int[10];
        for (char d : digits) {
            if (d > '0' && d <= '9') {
                count[d - '0']++;
            }
        }
        for (char d : digits) {
            if (d > '0' && d <= '9' && count[d - '0'] != d - '0') {
                return false;
            }
        }
        return true;
    }

    public static int nextBalanced(int n) {
        int current = n + 1;
        while (true) {
            if (isBalanced(current)) {
                return current;
            }
            current++;
        }
    }

    public static void main(String[] args) {
        System.out.println(nextBalanced(1));  // Output: 22
    }
}

This Python solution defines a helper function is_balanced to verify if a number is numerically balanced using a counter to count digit occurrences. The next_balanced function starts from n+1, checking each number using is_balanced until it finds a valid numerically balanced number.

Complexity

Time Complexity: O(T * D), where T is the number of numbers checked, and D is the number of digits per number.
Space Complexity: O(D), used for the counter.

Try this approach in the editor

Approach 2: Permutations with Digit Limits

This approach leverages generating permutations of digits up to a certain limit and checking if they form a numerically balanced number. This method is more efficient as it explores fewer possibilities by restricting digit occurrences.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool isBalanced(const vector<int>& digits) {
    vector<int> count(10, 0);
    for (int d : digits) {
        if (d != 0) {
            count[d]++;
        }
    }
    for (int d : digits) {
        if (d != 0 && count[d] != d) {
            return false;
        }
    }
    return true;
}

int nextBalanced(int n) {
    vector<int> startDigits;
    while (n > 0) {
        startDigits.push_back(n % 10);
        n /= 10;
    }
    reverse(startDigits.begin(), startDigits.end());
    
    for (int len = startDigits.size(); len <= 9; ++len) {
        vector<int> digits(len);
        function<bool(int, int)> generate = [&](int pos, int limit) -> bool {
            if (pos == len) {
                if (isBalanced(digits)) {
                    int num = 0;
                    for (int d : digits) num = num * 10 + d;
                    if (num > n) {
                        cout << num << endl;
                        return true;
                    }
                }
                return false;
            }
            for (int d = 1; d <= 9; ++d) {
                digits[pos] = d;
                if (generate(pos + 1, limit)) return true;
            }
            return false;
        };
        if (generate(0, len)) break;
    }
    return -1;
}

int main() {
    cout << nextBalanced(1) << endl;  // Output: 22
    return 0;
}

JavaScript

function isBalanced(x) {
    let count = Array(10).fill(0);
    let s = x.toString();
    for (let i = 0; i < s.length; i++) {
        let d = parseInt(s[i]);
        if (d > 0)
            count[d]++;
    }
    for (let i = 0; i < s.length; i++) {
        let d = parseInt(s[i]);
        if (d > 0 && count[d] !== d) {
            return false;
        }
    }
    return true;
}

function nextBalanced(n) {
    let limit = Math.pow(10, 6);
    for (let current = n + 1; current < limit; current++) {
        if (isBalanced(current)) {
            return current;
        }
    }
    return -1;
}

console.log(nextBalanced(1));  // Output: 22

In this C++ solution, we generate permutations of potential digit arrangements and test if they are numerically balanced. By iterating from smaller numbers, starting at n+1, and verifying digit counts, the code ensures we find the next balanced number efficiently.

Complexity

Time Complexity: Potentially O(9^D) where D is the number of digit positions considered bounded by digit limits.
Space Complexity: O(D), for storing the current permutation of digits.

Try this approach in the editor

Approach 3: 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).

TypeScript

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

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

Rust

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

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Search	Time Complexity: O(T * D), where T is the number of numbers checked, and D is the number of digits per number. Space Complexity: O(D), used for the counter.
Permutations with Digit Limits	Time Complexity: Potentially O(9^D) where D is the number of digit positions considered bounded by digit limits. Space Complexity: O(D), for storing the current permutation of digits.
Enumeration	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Search	O(k * d)	O(1)	Quick implementation when constraints are small and balanced numbers are sparse
Permutations with Digit Limits	O(P)	O(P)	Preferred approach when you want to generate only valid balanced numbers and avoid scanning every integer

Frequently asked questions

Is Next Greater Numerically Balanced Number easy or hard?

The problem is rated Medium because the definition is simple but the key insight involves recognizing strict digit-frequency constraints. Brute force is straightforward, while the optimized solution requires reasoning about enumeration and permutation generation.

Next Greater Numerically Balanced Number Python/Java solution

Python and Java implementations usually follow two patterns: brute force checking from n+1 using a digit counter, or generating balanced numbers via backtracking/permutations and selecting the smallest value greater than n. Both approaches fit comfortably within typical interview constraints.

How to solve Next Greater Numerically Balanced Number in O(n)?

A practical optimization is to precompute all numerically balanced numbers by generating valid digit-frequency combinations and permuting them. After generating the list, sort it and return the smallest value greater than n using binary search. The generation step is small and the lookup becomes O(log N).

What is the best approach for Next Greater Numerically Balanced Number?

The most efficient approach is generating valid numerically balanced numbers using digit-frequency constraints and permutations. Instead of checking every integer after n, you construct numbers where digit d appears exactly d times, generate their permutations, and return the smallest value greater than n.

Is Next Greater Numerically Balanced Number asked at Google/Amazon/Meta?

Problems involving digit frequency constraints, enumeration, and combinatorial generation appear in interviews at companies like Google, Amazon, and Meta. Variants that require generating numbers with specific digit counts are commonly used to test reasoning about constraints and search space reduction.

What data structure is used in Next Greater Numerically Balanced Number?

The solution mainly uses a digit frequency array of size 10 for validation and recursion or backtracking stacks for generating permutations. Arrays and simple lists are sufficient because the total number of candidate numbers is very small.

What is the time complexity of Next Greater Numerically Balanced Number?

The brute force method runs in roughly O(k * d), where k is the number of integers checked after n and d is the number of digits per number. The optimized enumeration approach runs in O(P), where P is the number of valid balanced permutations generated, which is very small in practice.

Next Greater Numerically Balanced Number solution and explanation

The problem

Approach overview

Approach 1: Brute Force Search

Approach 2: Permutations with Digit Limits

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Next Greater Numerically Balanced Number solution and explanation

The problem

Approach overview

Approach 1: Brute Force Search

Approach 2: Permutations with Digit Limits

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems