This is our solution and implementation to problem #2048: Next Greater Numerically Balanced Number on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Next Greater Numerically Balanced Number on LeetCode.
Problem Analysis
An integer n is considered to be numerically balanced if, for every distinct digit d in n, there are exactly d instances of that digit in n. This means numbers such as 22 and 3133 are balanced numbers, whereas 21 and 30331 are not. To check if any given number is numerically balanced, we can count the number of occurences of each digit, then check if each digit d occurs d times based on what we've counted. Since there is a maximum of 9 distinct digits which can appear in a number, we can use an int array to map each digit (index) to its count (value), then iterate from 0-9 to check if the condition is satisfied. With this knowledge, we could implement an algorithm to loop over integers, starting from n+1, and check each value until we find the next numerically balanced one. However, the naive version of this approach would redundantly re-count digits. In almost all cases, most digit counts will remain the same at each increment. With this in mind, we can modify the approach to re-use counts from previous iterations.
Implementation Strategy
We will be using a linked list to hold each digit of a given integer. The root node of the linked list will contain the digit to the right, and each subsequent node will contain digits to the left. In other words, the linked list holds the digits in reverse. We'll also have the head node store how many occurences of each digit occur in an array, where the index is the digit and the value is the number of occurences of that digit. The algorithm can be summarized as:
- Create the custom linked list numAsList and initialize it with n + 1:
- The linked list object will recursively create one node for each digit in the input number.
- Check if the number is a balanced number:
- Iterate over the digit counts array in numAsList. For each number, if it is not zero and not equal to the index in the array, then the number is not a balanced number.
- If no violations have been found, it is a balanced number.
- If it is a balanced number, return the int value of numAsList immediately and do not proceed to the steps below.
- Increment the value of numAsList:
- The head node will increment its digit value. If it's digit value is 9:
- Set it to 0.
- Call increment on the next node.
- If not, increment the current digit.
- The head node will increment its digit value. If it's digit value is 9:
At each iteration, we'll check the conditions to see if it's a balanced number, and if not, increment the value represented by the linked list. The linked list implementation will recursively update its nodes to properly set the digits and update the overall digit counts.
Space and Time Complexity
The space complexity is O(log n), as the linked list will take floor(log10(n)) nodes to store each digit in the input number. The time complexity is O(log n), as it will take a constant number of iterations to find each balanced number, and each iteration requires roughly floor(log10(n)) operations.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution. Other files are used as utilities to support the main implementation.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.