How hard is LeetCode 2048. Next Greater Numerically Balanced Number?

LeetCode 2048. Next Greater Numerically Balanced Number is rated Medium on LeetCode.

What is the time complexity of LeetCode 2048. Next Greater Numerically Balanced Number?

The Python solution on this page runs in O(M - n), where M = 1224444.

What is the space complexity of LeetCode 2048. Next Greater Numerically Balanced Number?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2048. Next Greater Numerically Balanced Number cover?

LeetCode 2048. Next Greater Numerically Balanced Number is tagged Hash Table, Math, Backtracking, Counting and Enumeration on LeetCode.

Next Greater Numerically Balanced Number — LeetCode 2048 Python Solution

MediumHash TableMathBacktrackingCountingEnumeration

Problem: #2048
Pattern: Backtracking
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: n = 1
Output: 22
Explanation: 22 is numerically balanced since:

Python solution

Python

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        for x in count(n + 1):
            y = x
            cnt = [0] * 10
            while y:
                y, v = divmod(y, 10)
                cnt[v] += 1
            if all(v == 0 or i == v for i, v in enumerate(cnt)):
                return x

Complexity

Measure	Complexity
Time	O(M - n), where M = 1224444
Space	O(1) auxiliary

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2048. Next Greater Numerically Balanced Number is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2048. Next Greater Numerically Balanced Number?: LeetCode 2048. Next Greater Numerically Balanced Number is rated Medium on LeetCode.
What is the time complexity of LeetCode 2048. Next Greater Numerically Balanced Number?: The Python solution on this page runs in O(M - n), where M = 1224444.
What is the space complexity of LeetCode 2048. Next Greater Numerically Balanced Number?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2048. Next Greater Numerically Balanced Number cover?: LeetCode 2048. Next Greater Numerically Balanced Number is tagged Hash Table, Math, Backtracking, Counting and Enumeration on LeetCode.