We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Next Greater Numerically Balanced Number

Difficulty: Medium

Problem 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.

Key Insights

  • A numerically balanced number must have the count of each digit equal to its value.
  • The digits 0-9 can only appear a limited number of times (0-9).
  • The smallest balanced number must be constructed starting from the least significant position to meet the "strictly greater" condition.
  • Backtracking can be used to explore combinations of digits while ensuring the numerically balanced property holds.

Space and Time Complexity

Time Complexity: O(10^n), where n is the number of digits in the number, as we may need to generate combinations of digits. Space Complexity: O(n), for storing the counts of digits and the resulting number.

Solution

To find the next greater numerically balanced number, we can utilize a backtracking approach. We will generate possible combinations of digits (from 1 to 9) and ensure that each digit d appears exactly d times. The algorithm will check each generated number to see if it is greater than n and will track the smallest valid number found.

  1. Use a backtracking method to try to place digits from 1 to 9.
  2. For each digit d, add it to the current number d times.
  3. If the formed number is greater than n and is numerically balanced, check if it is smaller than the current answer.
  4. Continue until all combinations are exhausted.

Code Solutions

def is_numerically_balanced(x):
    from collections import Counter
    digit_count = Counter(str(x))
    for d in digit_count:
        if digit_count[d] != int(d):
            return False
    return True

def next_greater_numerically_balanced(n):
    def backtrack(current, counts):
        if len(current) > 0:
            num = int(''.join(current))
            if num > n and is_numerically_balanced(num):
                results.append(num)
        for d in range(1, 10):
            if counts[d] < d:
                counts[d] += 1
                current.append(str(d))
                backtrack(current, counts)
                current.pop()
                counts[d] -= 1

    results = []
    backtrack([], [0] * 10)  # counts for digits 0-9
    return min(results) if results else -1  # return the smallest valid number
← Back to All Questions