LeetCode 2048 - Next Greater Numerically Balanced Number

The problem asks us to find the smallest integer strictly greater than n such that the number is numerically balanced. A number is numerically balanced when every digit that appears in the number appears exactly as many times as its value.

leetcodemediumhash-tablemathbacktrackingcountingenumeration

LeetCode Problem 2048

Difficulty: 🟡 Medium
Topics: Hash Table, Math, Backtracking, Counting, Enumeration

Solution

Problem Understanding

The problem asks us to find the smallest integer strictly greater than n such that the number is numerically balanced.

A number is numerically balanced when every digit that appears in the number appears exactly as many times as its value. For example:

  • 22 is balanced because digit 2 appears exactly 2 times.

  • 1333 is balanced because:

  • digit 1 appears once

  • digit 3 appears three times

  • 122 is not balanced because digit 1 appears once, which is correct, but digit 2 appears only twice, which is also correct, so actually 122 is balanced.

  • 1022 is not balanced because digit 0 appears once, but a balanced number would require digit 0 to appear zero times.

The input consists of a single integer n, and we must return the smallest balanced number strictly larger than it.

The constraint is:

0 <= n <= 10^6

This upper bound is relatively small. Since numerically balanced numbers are rare, this strongly suggests that we can either:

  1. Enumerate numbers and test them
  2. Generate all valid balanced numbers in advance

An important observation is that balanced numbers cannot be arbitrarily large under this constraint. Since n <= 10^6, the answer will also remain fairly small.

Several edge cases are important:

  • n = 0, the smallest answer is 1
  • Numbers containing zeroes can never be balanced unless zero appears zero times
  • Numbers with repeated digits that do not match the digit count must be rejected
  • The answer must be strictly greater than n, not greater than or equal
  • Very close values near the upper limit still have a small valid answer space

Approaches

Brute Force Approach

The most direct approach is to start from n + 1 and test every number one by one until we find a numerically balanced number.

For each candidate number:

  1. Count the occurrences of every digit
  2. Verify that every digit d appears exactly d times
  3. If valid, return the number

This approach is correct because it checks every integer in increasing order, so the first valid number encountered must be the smallest valid answer.

However, this solution is inefficient because many numbers are checked unnecessarily. Even though the constraint is only 10^6, repeatedly performing digit counting for many candidates can still be wasteful.

Optimal Approach

The key insight is that numerically balanced numbers are extremely rare.

A balanced number is completely determined by the digits it contains. For example:

  • If digit 2 exists, it must appear exactly twice
  • If digit 5 exists, it must appear exactly five times

This means the total number of possible balanced numbers is very small.

Instead of testing every integer, we can:

  1. Generate all possible numerically balanced numbers using backtracking
  2. Store them in a list
  3. Sort the list
  4. Find the smallest number greater than n

Because the search space is tiny, this approach is much faster and cleaner.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k * d) O(d) Checks every number after n, where d is digit count
Optimal O(M log M) preprocessing + O(M) query O(M) Generates only valid balanced numbers

Here:

  • k is the number of candidates checked
  • d is the number of digits
  • M is the total number of balanced numbers, which is very small

Algorithm Walkthrough

Step 1: Generate Valid Digit Sets

A balanced number can only contain digits 1 through 9.

For each digit included:

  • digit d must appear exactly d times

Examples:

  • choosing digit 2 contributes "22"
  • choosing digits 1 and 3 contributes "1333"

We use backtracking to try all subsets of digits.

Step 2: Build the Digit Multiset

For every chosen digit combination:

  • append digit d exactly d times

Example:

Digits chosen: [1, 3]
Constructed multiset: "1333"

Step 3: Generate All Unique Permutations

The arrangement of digits matters.

For example:

1333
3133
3313
3331

are all different balanced numbers.

We generate all unique permutations using backtracking.

Step 4: Convert Permutations into Integers

Each permutation is converted into an integer and added to a result set.

Using a set prevents duplicates.

Step 5: Sort All Balanced Numbers

After generation finishes:

  • convert the set into a sorted list

This allows efficient lookup of the next larger number.

Step 6: Find the Smallest Number Greater Than n

Traverse the sorted list and return the first value greater than n.

Since the list is ordered, this guarantees the smallest valid answer.

Why it works

The algorithm works because every numerically balanced number must satisfy a strict frequency rule:

digit d appears exactly d times

The backtracking process systematically generates every possible valid digit combination and every arrangement of those digits. Since all balanced numbers are included and the final list is sorted, the first number greater than n is guaranteed to be the correct answer.

Python Solution

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        balanced_numbers = set()

        def generate_digit_sets(start_digit, current_digits):
            if current_digits:
                chars = []

                for digit in current_digits:
                    chars.extend([str(digit)] * digit)

                used = [False] * len(chars)

                def generate_permutations(path):
                    if len(path) == len(chars):
                        balanced_numbers.add(int("".join(path)))
                        return

                    seen = set()

                    for i in range(len(chars)):
                        if used[i]:
                            continue

                        if chars[i] in seen:
                            continue

                        seen.add(chars[i])

                        used[i] = True
                        path.append(chars[i])

                        generate_permutations(path)

                        path.pop()
                        used[i] = False

                generate_permutations([])

            for digit in range(start_digit, 8):
                current_digits.append(digit)
                generate_digit_sets(digit + 1, current_digits)
                current_digits.pop()

        generate_digit_sets(1, [])

        sorted_numbers = sorted(balanced_numbers)

        for number in sorted_numbers:
            if number > n:
                return number

        return -1

The solution first generates all balanced numbers using recursive backtracking.

The generate_digit_sets function decides which digits will appear in the balanced number. If digit d is chosen, it must appear exactly d times.

After constructing the digit multiset, the algorithm generates all unique permutations. The seen set prevents duplicate permutations caused by repeated digits.

Every valid permutation is converted into an integer and inserted into balanced_numbers.

Once generation completes, the set is sorted. The algorithm then scans the sorted list and returns the first value strictly larger than n.

Because the total number of balanced numbers is small, preprocessing is efficient.

Go Solution

package main

import (
	"sort"
	"strconv"
)

func nextBeautifulNumber(n int) int {
	balancedNumbers := map[int]bool{}

	var generateDigitSets func(int, []int)

	generateDigitSets = func(startDigit int, currentDigits []int) {
		if len(currentDigits) > 0 {
			chars := []byte{}

			for _, digit := range currentDigits {
				for i := 0; i < digit; i++ {
					chars = append(chars, byte('0'+digit))
				}
			}

			used := make([]bool, len(chars))

			var generatePermutations func([]byte)

			generatePermutations = func(path []byte) {
				if len(path) == len(chars) {
					value, _ := strconv.Atoi(string(path))
					balancedNumbers[value] = true
					return
				}

				seen := map[byte]bool{}

				for i := 0; i < len(chars); i++ {
					if used[i] {
						continue
					}

					if seen[chars[i]] {
						continue
					}

					seen[chars[i]] = true

					used[i] = true
					path = append(path, chars[i])

					generatePermutations(path)

					path = path[:len(path)-1]
					used[i] = false
				}
			}

			generatePermutations([]byte{})
		}

		for digit := startDigit; digit <= 7; digit++ {
			currentDigits = append(currentDigits, digit)

			generateDigitSets(digit+1, currentDigits)

			currentDigits = currentDigits[:len(currentDigits)-1]
		}
	}

	generateDigitSets(1, []int{})

	numbers := []int{}

	for value := range balancedNumbers {
		numbers = append(numbers, value)
	}

	sort.Ints(numbers)

	for _, value := range numbers {
		if value > n {
			return value
		}
	}

	return -1
}

The Go implementation follows the same recursive structure as the Python version.

A map[int]bool is used instead of a Python set. Byte slices are used for efficient character manipulation during permutation generation.

Since Go does not provide built in permutation helpers, recursive backtracking is implemented manually. Slice resizing is handled carefully during backtracking to restore state correctly.

Integer overflow is not an issue because all generated numbers remain well within Go's integer range.

Worked Examples

Example 1

Input: n = 1

Generated balanced numbers begin with:

1
22
122
212
221
333
...

We scan in sorted order:

Number Greater Than 1?
1 No
22 Yes

Answer:

22

Example 2

Input: n = 1000

Relevant balanced numbers near 1000:

Number Balanced? Greater Than 1000?
333 Yes No
122 Yes No
1333 Yes Yes

The first valid number larger than 1000 is:

1333

Example 3

Input: n = 3000

Relevant balanced numbers:

Number Greater Than 3000?
1333 No
3133 Yes

Digit counts for 3133:

Digit Frequency
1 1
3 3

So the answer is:

3133

Complexity Analysis

Measure Complexity Explanation
Time O(M log M) Sorting all generated balanced numbers
Space O(M) Stores all balanced numbers

The total number of numerically balanced numbers is very small because each digit imposes a strict frequency constraint. Therefore, even exhaustive generation remains efficient.

Permutation generation is bounded because the total digit count never becomes large under the problem constraints.

Test Cases

solution = Solution()

assert solution.nextBeautifulNumber(1) == 22        # basic example
assert solution.nextBeautifulNumber(1000) == 1333   # mixed digits
assert solution.nextBeautifulNumber(3000) == 3133   # another mixed arrangement

assert solution.nextBeautifulNumber(0) == 1         # smallest possible input
assert solution.nextBeautifulNumber(21) == 22       # next immediate balanced number
assert solution.nextBeautifulNumber(22) == 122      # strictly greater condition
assert solution.nextBeautifulNumber(122) == 212     # permutation ordering
assert solution.nextBeautifulNumber(999999) > 999999  # upper range stress test

assert solution.nextBeautifulNumber(300) == 333     # repeated single digit
assert solution.nextBeautifulNumber(4000) == 4444   # exact repeated digit case
assert solution.nextBeautifulNumber(5000) == 14444  # multiple digit frequencies

Test Summary

Test Why
n = 1 Basic functionality
n = 1000 Mixed digit balanced number
n = 3000 Permutation handling
n = 0 Minimum boundary
n = 21 Small next answer
n = 22 Strictly greater requirement
n = 122 Different valid permutation
n = 999999 Large input stress case
n = 300 Single repeated digit
n = 4000 Exact frequency repetition
n = 5000 Multi digit balanced construction

Edge Cases

One important edge case is when n = 0. Since 1 is itself numerically balanced because digit 1 appears exactly once, the correct answer is 1. A buggy implementation might incorrectly skip single digit balanced numbers.

Another tricky case is when the input itself is already balanced. For example:

n = 22

The answer cannot be 22 because the problem requires a strictly greater value. The implementation handles this correctly by scanning for the first number satisfying:

number > n

rather than >=.

A third important edge case involves zeroes. Any number containing digit 0 is invalid unless zero appears exactly zero times, which is impossible once it exists in the number. For example:

1022

is not balanced because digit 0 appears once. The generation approach naturally avoids this issue because digit 0 is never included during construction.

Another subtle case is duplicate permutations. For example, the multiset:

3331

contains repeated digits. Without duplicate prevention, permutation backtracking would generate many identical arrangements repeatedly. The seen set inside the permutation recursion prevents duplicate work and ensures efficiency.