# Next Greater Numerically Balanced Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/next-greater-numerically-balanced-number)
Canonical: https://scaleengineer.com/dsa/problems/next-greater-numerically-balanced-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Counting](https://scaleengineer.com/dsa/patterns/counting), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Hash Table
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## 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 <= 106`

# Approaches
## 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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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.

## Permutation Generation
Instead of checking every number, we can generate only the numerically balanced numbers. This is possible because the properties of these numbers constrain their structure. We can determine the possible combinations of digits that can form a balanced number and then generate all permutations of these digits.
**Time:** O(1). The number of compositions and permutations for numbers up to 7 digits is a fixed, small constant. The entire generation process runs in time independent of the input `n`. · **Space:** O(1). The recursion depth for both composition and permutation generation is bounded by a small constant (7), and the space used to store digits is also minimal.
**Pros:** Very efficient as it doesn't check any non-balanced numbers.; The time complexity is constant with respect to the input `n`.
**Cons:** Significantly more complex to implement correctly compared to the brute-force approach.; The permutation generation logic can be tricky to get right, especially with duplicate digits.
### Explanation
This approach is based on the observation that the number of numerically balanced numbers is small. We can define the properties of such numbers and generate them directly. A number is balanced if its length is equal to the sum of its unique digits. Since the maximum `n` is `10^6`, the result will not be extremely large (it's `1224444`), meaning we only need to consider numbers up to 7 digits.

The process involves two main steps: first, find all possible sets of unique digits `{d1, d2, ...}` whose sum is 7 or less. These are known as integer partitions. For each valid partition, we construct the full set of digits (e.g., for `{1,3}`, we get `{1,3,3,3}`). Then, we generate all unique permutations of these digits, form numbers, and find the smallest one that is greater than `n`.

```java
class Solution {
    long ans = Long.MAX_VALUE;
    int limit;

    public int nextBeautifulNumber(int n) {
        this.limit = n;
        findCompositions(0, new ArrayList<>());
        return (int) ans;
    }

    // Recursively find compositions of digits whose sum is <= 7
    private void findCompositions(int currentSum, List<Integer> digits) {
        if (currentSum > 0) {
            StringBuilder sb = new StringBuilder();
            for (int d : digits) {
                for (int i = 0; i < d; i++) sb.append(d);
            }
            generatePermutations(sb.toString().toCharArray(), 0);
        }

        for (int d = 1; d <= 9; d++) {
            if (!digits.contains(d) && currentSum + d <= 7) {
                digits.add(d);
                findCompositions(currentSum + d, digits);
                digits.remove(digits.size() - 1); // backtrack
            }
        }
    }

    // Generate all unique permutations of the given digits
    private void generatePermutations(char[] s, int index) {
        if (index == s.length) {
            long num = Long.parseLong(new String(s));
            if (num > limit) {
                ans = Math.min(ans, num);
            }
            return;
        }
        Set<Character> seen = new HashSet<>();
        for (int i = index; i < s.length; i++) {
            if (seen.contains(s[i])) continue;
            seen.add(s[i]);
            swap(s, index, i);
            generatePermutations(s, index + 1);
            swap(s, index, i); // backtrack
        }
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
```
### Algorithm
*   The core idea is to generate only the numbers that can be numerically balanced, avoiding the check for all integers.
*   A number is numerically balanced if the sum of its unique digits equals the total number of digits. For example, for `1333`, the unique digits are `{1, 3}`, their sum is `1+3=4`, and the number has 4 digits.
*   Since `n <= 10^6`, the answer will have at most 7 digits (the next balanced number is `1224444`).
*   We can find all sets of unique digits (partitions) whose sum is between 1 and 7.
    *   e.g., for a sum of 4, the partitions are `{4}` and `{1, 3}`.
*   For each partition, construct the multiset of digits.
    *   e.g., for `{1, 3}`, the multiset is `{1, 3, 3, 3}`.
*   Generate all unique permutations of this multiset. A backtracking algorithm is suitable for this.
*   Each permutation forms a candidate number. Keep track of the smallest candidate found so far that is strictly greater than `n`.

## Pre-computed Hardcoded List
This is the most efficient approach at runtime. Given the small and fixed set of numerically balanced numbers within the problem's range, we can pre-compute them all and hardcode them into our solution. The problem then reduces to a simple search in a small, sorted list.
**Time:** O(1). The search is performed on a fixed-size list. A linear scan takes a constant number of operations. · **Space:** O(1), as the list is of a fixed, constant size.
**Pros:** Extremely fast runtime performance, as it only involves a simple search in a small array.; The runtime logic is very simple and easy to verify.
**Cons:** The solution contains a hardcoded list of 'magic numbers', which might be considered poor practice without proper context or explanation.; The list needs to be generated correctly beforehand, which is a one-time effort but requires a correct implementation.
### Explanation
The number of numerically balanced integers is finite and small within the constraints of the problem (`n <= 10^6`). The smallest balanced number greater than `10^6` is `1224444`. We can pre-generate all balanced numbers up to this value and store them in a sorted array. This pre-computation can be done once, offline. The final solution then simply includes this hardcoded list.

When the `nextBeautifulNumber` function is called, it iterates through this static, sorted list and returns the first number it finds that is larger than the input `n`. Due to the small size of the list (around 60-70 numbers), a simple linear scan is extremely fast.

```java
class Solution {
    // A pre-computed and sorted list of all numerically balanced numbers up to 1224444.
    private static final int[] BEAUTIFUL_NUMBERS = {
        1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 
        22333, 23233, 23323, 32233, 32323, 33223, 41444, 44144, 44414, 
        44441, 55555, 122333, 132233, 133223, 155555, 212333, 213233, 
        213323, 221333, 223133, 223313, 224444, 231233, 231323, 232133, 
        232313, 233123, 233213, 242444, 244244, 312233, 312323, 313223, 
        321233, 321323, 322133, 322313, 323123, 323213, 331223, 332123, 
        332213, 414444, 422444, 424244, 441444, 442244, 444144, 444414, 
        515555, 551555, 555155, 555515, 666666, 1224444
    };

    public int nextBeautifulNumber(int n) {
        for (int num : BEAUTIFUL_NUMBERS) {
            if (num > n) {
                return num;
            }
        }
        return -1; // Should not be reached given n <= 10^6
    }
}
```
### Algorithm
*   Generate all numerically balanced numbers up to the maximum possible answer. Since `n <= 10^6`, the next balanced number is `1224444`. So we need all balanced numbers up to this value.
*   This generation can be done offline using the permutation generation method from the second approach.
*   Store these numbers in a sorted, hardcoded array within the program.
*   Given the input `n`, perform a linear scan (or binary search) on this array.
*   Return the first number found in the array that is strictly greater than `n`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def nextBeautifulNumber(self, n: int) -> int: for x in count(n + 1): y = x cnt = [0] * 10 while y: y, v = divmod(y, 10) cnt[v] += 1 if all(v == 0 or i == v for i, v in enumerate(cnt)): return x

```