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 1:
Input: n = 1 Output: 22 Explanation: 22 is numerically balanced since: - The digit 2 occurs 2 times. It is also the smallest numerically balanced number strictly greater than 1.
Example 2:
Input: n = 1000 Output: 1333 Explanation: 1333 is numerically balanced since: - The digit 1 occurs 1 time. - The digit 3 occurs 3 times. It is also the smallest numerically balanced number strictly greater than 1000. Note that 1022 cannot be the answer because 0 appeared more than 0 times.
Example 3:
Input: n = 3000 Output: 3133 Explanation: 3133 is numerically balanced since: - The digit 1 occurs 1 time. - The digit 3 occurs 3 times. It is also the smallest numerically balanced number strictly greater than 3000.
Constraints:
0 <= n <= 106This method involves incrementing the number starting from n+1 and checking each number to see if it is numerically balanced. This approach is straightforward but not optimal as it checks each number one by one.
This Python solution defines a helper function is_balanced to verify if a number is numerically balanced using a counter to count digit occurrences. The next_balanced function starts from n+1, checking each number using is_balanced until it finds a valid numerically balanced number.
Java
Time Complexity: O(T * D), where T is the number of numbers checked, and D is the number of digits per number.
Space Complexity: O(D), used for the counter.
This approach leverages generating permutations of digits up to a certain limit and checking if they form a numerically balanced number. This method is more efficient as it explores fewer possibilities by restricting digit occurrences.
In this C++ solution, we generate permutations of potential digit arrangements and test if they are numerically balanced. By iterating from smaller numbers, starting at n+1, and verifying digit counts, the code ensures we find the next balanced number efficiently.
JavaScript
Time Complexity: Potentially O(9^D) where D is the number of digit positions considered bounded by digit limits.
Space Complexity: O(D), for storing the current permutation of digits.
| Approach | Complexity |
|---|---|
| Brute Force Search | Time Complexity: O(T * D), where T is the number of numbers checked, and D is the number of digits per number. |
| Permutations with Digit Limits | Time Complexity: Potentially O(9^D) where D is the number of digit positions considered bounded by digit limits. |
Next Greater Element | Two Variants | Leetcode • take U forward • 265,567 views views
Watch 9 more video solutions →Practice Next Greater Numerically Balanced Number with our built-in code editor and test cases.
Practice on FleetCode