Next Greater Numerically Balanced Number

MEDIUM

Description

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⁶

Approaches

Checkout 3 different approaches to solve Next Greater Numerically Balanced Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Next Greater Numerically Balanced Number. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Next Greater Numerically Balanced Number

Patterns:

MathBacktrackingCountingEnumeration

Data Structures:

Hash Table

Companies:

Sprinklr |