Problem Statement in English

You’re given an integer n.

A numerically balanced number is a number where for every digit d in the number, there are exactly d occurrences of that digit in the number. For example, 22 is numerically balanced because the digit 2 occurs exactly twice, while 1233 is not because the digit 1 occurs once, the digit 2 occurs twice, and the digit 3 occurs thrice.

Approach

Once you look at the constrains and also, the problem statement, you realise that there are a very finite number of numerically balanced numbers. We only need to check until 10^9, since 9 must occur 9 times to be valid.

After that it’s just implementation.

Solution in Python


class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        def check(state):
            hm = [0] * 10

            while state > 0:
                hm[state % 10] += 1
                state //= 10

            for j in range(10):
                if hm[j] and hm[j] != j:
                    return False
                    
            return True

        for i in range(n + 1, 10**9):
            if check(i):
                return i

Complexity

  • Time: O(n)O(n)
    Since we are iterating from n to 10^9 in worst case.

  • Space: O(1)O(1)
    Since we are using constant space.

And we are done.