Next Greater Numerically Balanced Number - Practice Coding Problems

Next Greater Numerically Balanced Number - 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.

For example:

122 is numerically balanced because digit 1 appears exactly 1 time, and digit 2 appears exactly 2 times.
1223 is not numerically balanced because digit 1 appears 1 time, digit 2 appears 2 times, but digit 3 appears 1 time (not 3 times).

Given an integer n, return the smallest numerically balanced number strictly greater than n.

Input & Output

Example 1 — Basic Case

$ Input: n = 1

› Output: 22

💡 Note: The next numerically balanced number after 1 is 22, where digit 2 appears exactly 2 times.

Example 2 — Find Next Pattern

$ Input: n = 1000

› Output: 1333

💡 Note: After 1000, the next balanced number is 1333, where digit 1 appears 1 time and digit 3 appears 3 times.

Example 3 — Already Large

$ Input: n = 3000

› Output: 3133

💡 Note: The next balanced number is 3133, which is a permutation of digits 1 and 3 maintaining the balance property.

Constraints

0 ≤ n ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Given number n

Process

Find next number where each digit d appears d times

Output

Smallest balanced number > n

Key Takeaway

🎯 Key Insight: Only specific digit patterns can form balanced numbers, making precomputed lookup the most efficient solution

Asked in

G Google 25 f Meta 18

The key insight is that numerically balanced numbers follow specific patterns where digit d appears exactly d times. The most efficient approach uses precomputed patterns with binary search. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Number	O(k × log k)	O(1)	Increment from n+1 and check if each number is numerically balanced
Pattern-Based Generation	O(1)	O(1)	Generate balanced numbers using known patterns like 122, 1333, 24444, etc.
Backtracking - Generate Valid Numbers	O(9^k)	O(k)	Generate numerically balanced numbers using backtracking with digit constraints

Brute Force - Check Every Number — Algorithm Steps

Start with current = n + 1
For each number, count digit frequencies
Check if each digit d appears exactly d times
Return first balanced number found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n+1

Check

Count digits and verify balance condition

Result

Return first balanced number found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isBalanced(int num) {
    char s[20];
    sprintf(s, "%d", num);
    int count[10] = {0};
    
    for (int i = 0; s[i]; i++) {
        count[s[i] - '0']++;
    }
    
    for (int i = 0; s[i]; i++) {
        int digit = s[i] - '0';
        if (digit == 0 || count[digit] != digit) {
            return false;
        }
    }
    return true;
}

int solution(int n) {
    int current = n + 1;
    while (1) {
        if (isBalanced(current)) {
            return current;
        }
        current++;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × log k)

Where k is the distance to next balanced number, log k for digit counting

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for digit counting

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler