Skip to main content
Talentd

Next Greater Numerically Balanced Number - Solution & Explanation

MediumMathBacktrackingEnumeration11 min readAsked at: Microsoft, Meta, Google +2
Practice this problem

Problem Statement

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

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 107), 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.

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.

Code

PythonJava

Python

Java

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.

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.

Code

C++JavaScript

C++

JavaScript

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

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

Video Solution

Next Greater Numerically Balanced Number | Most Optimal Solution | LeetCode 2048 • Sanyam IIT Guwahati • 1,916 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Next Greater Numerically Balanced Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Width of Columns of a Grid