Scale Engineer

Next Greater Numerically Balanced Number

Med
#1865Time: O(K * log(N)), where `N` is the number being checked and `K` is the distance from `n` to the next numerically balanced number. Given `n <= 10^6`, the next balanced number is at most `1224444`. So `K` is at most `~2.2 * 10^5`. The `log(N)` factor comes from counting the digits of each number. This is efficient enough to pass within typical time limits.Space: O(1), as the frequency map used for checking a number has a fixed size of 10. If converting the number to a string, space is O(log10(N)), but this is also very small.1 company
Patterns
MathBacktrackingCountingEnumeration
Data structures
Hash Table
Companies
Sprinklr

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves checking every integer starting from n + 1 one by one until a numerically balanced number is found. For each number, a helper function determines if it meets the criteria of being numerically balanced.

Algorithm

  • Start a loop with a variable num, initialized to n + 1.
  • In each iteration, check if num is a numerically balanced number using a helper function.
  • The helper function isNumericallyBalanced(int num) works as follows:
    1. Create a frequency map (e.g., an array of size 10) to count the occurrences of each digit in num.
    2. Convert the number to a string or use modulo/division to iterate through its digits and populate the frequency map.
    3. Iterate through the frequency map from d = 0 to 9.
    4. If a digit d is present in the number (i.e., its count is greater than 0), check if its count is equal to d.
    5. If count[d] > 0 and count[d] != d for any d, the number is not balanced. Note that this implicitly handles the case for d=0, as count[0] must be 0 for a number to be balanced.
  • If isNumericallyBalanced(num) returns true, then num is the smallest balanced number greater than n. Return num.
  • If not, increment num and continue the loop.

Walkthrough

The most straightforward way to solve this problem is to iterate upwards from n + 1. For each number, we perform a check to see if it's numerically balanced. A number is numerically balanced if, for every digit d it contains, the digit d appears exactly d times. For instance, 22 is balanced because the digit 2 appears twice. 1333 is balanced because 1 appears once and 3 appears three times. An important detail is that the digit 0 cannot be in a numerically balanced number, because if it were, it would have to appear 0 times, which is a contradiction. The loop continues until the first such number is found, which is guaranteed to be the smallest one greater than n.

class Solution {    public int nextBeautifulNumber(int n) {        int num = n + 1;        while (true) {            if (isNumericallyBalanced(num)) {                return num;            }            num++;        }    }     private boolean isNumericallyBalanced(int num) {        int[] counts = new int[10];        String s = String.valueOf(num);        for (char c : s.toCharArray()) {            counts[c - '0']++;        }         // For a number to be numerically balanced, for every digit d in it,        // the count of d must be equal to d.        for (int i = 0; i < 10; i++) {            if (counts[i] > 0 && counts[i] != i) {                return false;            }        }        return true;    }}

Complexity

Time

O(K * log(N)), where `N` is the number being checked and `K` is the distance from `n` to the next numerically balanced number. Given `n <= 10^6`, the next balanced number is at most `1224444`. So `K` is at most `~2.2 * 10^5`. The `log(N)` factor comes from counting the digits of each number. This is efficient enough to pass within typical time limits.

Space

O(1), as the frequency map used for checking a number has a fixed size of 10. If converting the number to a string, space is O(log10(N)), but this is also very small.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal memory.

Cons

  • Can be slow if the gap between n and the next numerically balanced number is large.

Solutions

class Solution {public  int nextBeautifulNumber(int n) {    for (int x = n + 1;; ++x) {      int[] cnt = new int[10];      for (int y = x; y > 0; y /= 10) {        ++cnt[y % 10];      }      boolean ok = true;      for (int y = x; y > 0; y /= 10) {        if (y % 10 != cnt[y % 10]) {          ok = false;          break;        }      }      if (ok) {        return x;      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem