Next Greater Numerically Balanced Number

main.md

Question

Approach

I simply search upward from n+1 until I find a number that is numerically balanced. For each candidate number I count its digits; if any '0' appears I reject it immediately (because 0 would have to appear zero times) and otherwise I check that for every digit d present, its frequency equals d.

Implementation

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        def is_balanced(x: int) -> bool:
            s = str(x)
            if '0' in s:
                return False
            cnt: Dict[str,int] = {}
            for ch in s:
                cnt[ch] = cnt.get(ch, 0) + 1
            for ch, c in cnt.items():
                if c != int(ch):
                    return False
            return True

        x = n + 1
        while True:
            if is_balanced(x):
                return x
            x += 1

Complexities

• Time: O(L)
• Space: O(n)