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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Next Greater Numerically Balanced Number

Number: 2174

Difficulty: Medium

Paid? No

Companies: Sprinklr

Problem Description

An integer x is numerically balanced if for every digit d in x, the digit d appears exactly d times. Given an integer n, return the smallest numerically balanced number strictly greater than n.

Key Insights

  • A number is numerically balanced if for every unique nonzero digit d, its frequency in the number is exactly d.
  • Since digits are from 1 to 9, if digit d is included in the number, it must occur exactly d times.
  • Any numerically balanced number can be viewed as a multiset composed of digits d where each d appears d times.
  • Rather than checking every number after n, we can generate all candidate balanced numbers by considering every non-empty subset of {1, 2, …, 9} and forming the smallest permutation (by sorting) from the multiset.
  • Because n is at most 10^6, the list of candidate balanced numbers generated (which is very limited in count) can be precomputed and then searched to find the smallest candidate > n.

Space and Time Complexity

Time Complexity: O(1)
(Since there are at most 2^9−1 = 511 subsets and each candidate is computed in constant time, the overall candidate list is fixed and independent from n.)
Space Complexity: O(1)
(The space used for storing the list of candidates is fixed and small.)

Solution

We solve the problem by precomputing all numerically balanced numbers. For each non-empty subset of digits from 1 to 9, if a subset S is chosen then the balanced number is formed by adding each digit d exactly d times. The smallest numeric value that can be formed from that multiset is obtained by sorting the digits in increasing order. Once we have the list of all such candidate numbers, we sort the list and find the first candidate that is strictly greater than n.

Key data structures and steps:

  • Use an array (or list) to store candidate numbers.
  • Use bitmask or recursion/backtracking to generate each non-empty subset of {1,2,...,9}.
  • For each subset, for every digit d in the subset, append the character representation of d repeated d times.
  • Sort the digits in the assembled list to get the smallest number from those digits.
  • Convert the sorted string to an integer candidate.
  • Finally, sort all candidates and return the first candidate greater than n.

A careful point is ensuring that we use only digits 1 through 9 (digit 0 is not considered because including it would require 0 occurrences, which is contradictory).

Code Solutions

# Python solution

class Solution:
    def nextBalancedNumber(self, n: int) -> int:
        candidates = []  # List to store all numerically balanced numbers
        
        # There are 2^9 - 1 possible non-empty subsets of digits 1 to 9.
        for mask in range(1, 1 << 9):
            digits = []
            # Check each digit from 1 to 9; if bit is set include this digit.
            for d in range(1, 10):
                if mask & (1 << (d - 1)):
                    # Append digit d exactly d times as a string.
                    digits.extend([str(d)] * d)
            # Sort digits to form the smallest number from these multiset digits.
            candidate_str = ''.join(sorted(digits))
            candidate = int(candidate_str)
            candidates.append(candidate)
        
        # Remove duplicates and sort the candidate numbers.
        candidates = sorted(set(candidates))
        # Find the smallest candidate strictly greater than n.
        for candidate in candidates:
            if candidate > n:
                return candidate
        return -1  # Should never happen given the problem constraints

# Example usage:
# sol = Solution()
# print(sol.nextBalancedNumber(1))  # Output: 22
← Back to All Questions