Leetcode 2048: Next Greater Numerically Balanced Number
An integer x is numerically balanced if, for every digit d in x, the digit d occurs exactly d times in the number. For example, 22 is numerically balanced because the digit 2 appears exactly 2 times, while 3133 is numerically balanced because the digit 3 appears exactly 3 times, and the digit 1 appears exactly 1 time.
Given an integer n, find the smallest numerically balanced integer that is strictly greater than n.
Problem
Approach
Steps
Complexity
Input: A single integer n.
Example: Input: n = 5
Constraints:
• 0 <= n <= 10^6
Output: A single integer representing the smallest numerically balanced number strictly greater than n.
Example: Output: 22
Constraints:
• The output must always be a numerically balanced number.
Goal: Identify the smallest numerically balanced number greater than the input number n.
Steps:
• Generate a pre-defined list of known numerically balanced numbers.
• Iterate through the list to find the smallest number that is greater than n.
• Use permutations to explore numbers of the same digit length, ensuring they are numerically balanced.
Goal: Ensure that the numerically balanced property is satisfied for the output.
Steps:
• The digits in the number must occur the exact number of times as their value.
• The number must be strictly greater than n.
Assumptions:
• The input n is a valid integer within the given range.
• The numerically balanced property applies only to positive integers.
• Input: Input: n = 7
• Explanation: The smallest numerically balanced number greater than 7 is 22. The digit 2 occurs exactly 2 times. Output: 22.
• Input: Input: n = 2000
• Explanation: The smallest numerically balanced number greater than 2000 is 3133. The digit 3 occurs exactly 3 times, and the digit 1 occurs exactly 1 time. Output: 3133.
• Input: Input: n = 50000
• Explanation: The smallest numerically balanced number greater than 50000 is 122333. The digit 1 occurs exactly 1 time, digit 2 occurs 2 times, and digit 3 occurs 3 times. Output: 122333.
Approach: Use a precomputed list of numerically balanced numbers combined with permutation-based exploration for numbers of appropriate size.
Observations:
• Numerically balanced numbers are rare, making a precomputed list an efficient starting point.
• The problem involves a combination of string manipulation and numerical properties.
• Precomputing smaller numerically balanced numbers can drastically reduce runtime for queries involving smaller values of n.
Steps:
• Create a base list of precomputed numerically balanced numbers.
• For numbers shorter than n's digit length, directly find the result from the precomputed list.
• For numbers of the same length as n, use permutations to generate candidates and validate them.
• Return the smallest valid candidate that is strictly greater than n.
Empty Inputs:
• Not applicable as the problem guarantees a valid input.
Large Inputs:
• Handle cases where n is close to 10^6 by ensuring efficient traversal of balanced numbers.
Special Values:
• Values like n = 0 or n = 1, where the smallest balanced number is from the start of the list.
• Values just below a balanced number like n = 21 or n = 132.
Constraints:
• Ensure no numerically balanced numbers are skipped due to incorrect comparison.
vector<int> base = {1, 22, 122, 333, 1333, 4444, 14444, 22333, 55555, 122333, 155555, 224444, 666666 };
int nextBeautifulNumber(int n) {
int res = 1224444;
string s = to_string(n);
for(auto it: base) {
string ss = to_string(it);
if(ss.size() < s.size()) continue;
if(ss.size() > s.size()) res = min(res, it);
else {
do {
if(ss > s) {
res = min(res, stoi(ss));
}
} while(next_permutation(ss.begin(), ss.end()));
}
}
return res;
}
1 : Base Numbers Initialization
vector<int> base = {1, 22, 122, 333, 1333, 4444, 14444, 22333, 55555, 122333, 155555, 224444, 666666 };
Defines a vector `base` that contains a set of base 'beautiful' numbers, which will be used to find the next 'beautiful' number larger than the given input `n`.
2 : Function Declaration
int nextBeautifulNumber(int n) {
Declares the function `nextBeautifulNumber` that takes an integer `n` as input and returns the next beautiful number greater than `n`.
3 : Result Initialization
int res = 1224444;
Initializes the result `res` to the smallest base beautiful number that is larger than any possible input.
4 : String Conversion
string s = to_string(n);
Converts the input integer `n` into a string `s` to facilitate comparison with other string-based beautiful numbers.
5 : Loop Through Base Numbers
for(auto it: base) {
Iterates through each number in the `base` vector to check if it can be the next beautiful number larger than `n`.
6 : Convert Base Number to String
string ss = to_string(it);
Converts the current base number `it` into a string `ss` for comparison with the input string `s`.
7 : Size Comparison (Smaller)
if(ss.size() < s.size()) continue;
If the size of the current base number `ss` is smaller than `s`, skips it, as we are looking for a number with at least the same number of digits as `n`.
8 : Size Comparison (Larger)
if(ss.size() > s.size()) res = min(res, it);
If the size of the current base number `ss` is larger than `s`, it automatically becomes a candidate for the result `res` as the smallest larger 'beautiful' number.
9 : Exact Size Comparison
else {
If the base number `ss` has the same number of digits as `n`, the code enters this block to compare the numbers in more detail.
10 : Permutation Loop
do {
Starts a `do-while` loop that generates all permutations of the string `ss` to find the smallest valid 'beautiful' number greater than `s`.
11 : Permutation Comparison
if(ss > s) {
Compares the current permutation `ss` with the input string `s`. If `ss` is greater than `s`, it could be the next valid 'beautiful' number.
12 : Update Result
res = min(res, stoi(ss));
Updates the result `res` with the minimum of the current result and the integer value of the valid permutation `ss`.
13 : Next Permutation
} while(next_permutation(ss.begin(), ss.end()));
Generates the next permutation of the string `ss` and continues the loop until all permutations have been checked.
14 : Return Result
return res;
Returns the smallest 'beautiful' number greater than the input `n`.
Best Case: O(1) for direct lookup in the precomputed list.
Average Case: O(k * m!) for permutations, where k is the number of digits and m is the average digit count.
Worst Case: O(k * m!) when n is close to the largest precomputed number and requires exploration.
Description: Precomputing balanced numbers saves time, but larger inputs require exploring permutations for validation.
Best Case: O(1) if only precomputed results are used.
Worst Case: O(k) for storing temporary permutations.
Description: Space usage depends on the need for generating and validating permutations.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus