2048. Next Greater Numerically Balanced Number


Problem Description

An integer is considered numerically balanced if for each digit d that appears in the number, there are exactly d occurrences of that digit within the number itself. For example, the number 122 is numerically balanced because there is exactly one 1 and two 2s.

The problem at hand involves finding the smallest numerically balanced number that is strictly greater than a given integer n. That means if n is 1, then the next numerically balanced number is 22 because it's the smallest number greater than 1 that satisfies the numerically balanced condition (two instances of the digit 2).

Flowchart Walkthrough

Let's analyze the problem using the provided algorithm flowchart. Hereā€™s how we can establish the appropriate algorithm:

  1. Is it a graph?

    • No: The problem doesn't involve nodes and edges typically found in graph-related problems.
  2. Need to solve for kth smallest/largest?

    • No: This problem is not about finding the kth smallest or largest element.
  3. Involves Linked Lists?

    • No: There's no mention or use of linked lists in this problem.
  4. Does the problem have small constraints?

    • Yes: The numerically balanced number within the given constraints suggests we should explore candidate numbers within a manageable range.
  5. Brute force / Backtracking?

    • Yes: Since brute force or backtracking is a recommended approach for managing smaller constraint problems where we explore various configurations, it fits well for finding such specific numerically balanced numbers.

Conclusion: The flowchart suggests that a Brute force or Backtracking pattern is appropriate for generating and testing numbers to find the next greater numerically balanced number.

Intuition

The intuition behind the solution is to start from the number immediately greater than n and check each successive number to see if it meets the criteria of being numerically balanced. This is essentially a brute-force approach since it examines each number one by one until it finds the solution.

The function check(num) assesses whether a number num is numerically balanced. It creates a list counter that keeps track of the occurrences of each digit. The number is converted into a string to iterate over its digits, updating counter accordingly. Following that, the function verifies whether the occurrence of each digit in counter matches its value, thus confirming the number is numerically balanced or not.

This method is not the most efficient solution, particularly for large n, because it potentially evaluates many numbers until it finds the next numerically balanced number. However, it's a straightforward and easy-to-understand approach.

Learn more about Math and Backtracking patterns.

Solution Approach

The solution uses a straightforward brute-force approach. Here's a step-by-step guide to how the algorithm is implemented:

  1. Validation Function (check): A key part of the solution is the check function, which takes an integer num as input and determines if num is numerically balanced. The function does the following:

    • Initialize a counter list of 10 zeros, with each index representing digits 0 to 9.
    • Convert num to a string to iterate over its digits.
    • Increment the counter at the index corresponding to each digit d by 1 for each occurrence of d in num.
    • Iterate over the digits of num again, and for each digit d, check if counter[d] is equal to the digit d itself. This step confirms that the number of occurrences of each digit d is equal to its value.
    • If any digit d does not meet the balance condition, return False.
    • If all digits satisfy the condition, return True indicating the number is numerically balanced.
  2. Main Function (nextBeautifulNumber): This function looks for the smallest numerically balanced number strictly greater than n.

    • Start iterating from n+1, since we are looking for a number strictly greater than n.
    • Call the check function for each number i in the iteration.
    • Stop the iteration and return the current number i as soon as a numerically balanced number is found.
    • The upper limit of 10**7 is an arbitrary large number to ensure that the next numerically balanced number is found within practical computational time.
  3. Efficiency: While the provided approach is correct, it's important to note that the efficiency isn't optimal for large numbers because it may require checking a large number of candidates. Advanced techniques or optimizations such as precomputing possible balanced numbers or using combinatorics to generate candidates more intelligently could potentially improve efficiency.

The algorithm uses iteration and simple counting, making it easily understandable. The check function uses a list as a counting mechanism, which is an instance of the array data structure, and the iterations over the sequence of numbers and their digits are basic patterns used in brute-force algorithm implementations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take an integer n = 300. According to the problem description, we need to find the smallest numerically balanced number greater than n.

Starting from 301 (the next integer after n), we apply check(num) to each subsequent integer:

  1. Check 301: Is there one 3, zero 0's, and one 1? No, because there has to be zero 0's (which is correct) but also three 3's and one 1, so 301 is not numerically balanced.

  2. Check 302, 303, ..., up until 312: None of these numbers will be numerically balanced because there will never be three 3s, or two 2s until at least 322 (the instance where the digit matches its count).

  3. Check 312: It is not numerically balanced either because there's only one 1 and one 3, but there should be three 3s and one 1.

  4. Skip forward to 322: This is the first number where the digit 2 appears twice, satisfying its requirement. But we need three occurrences of 3 and none of the numbers 313 to 322 meet this criteria.

Proceeding with this method, the first number to satisfy the checking criteria after 300 is 333. In 333, there are exactly three 3s, which meets the requirement of being numerically balanced.

This example shows that the check function will iterate over the numbers 301, 302, 303, ..., 332, 333, and when it reaches 333, it will return True, indicating that this is the smallest numerically balanced number greater than 300. The number 333 will then be returned by the nextBeautifulNumber function.

Thus, applying the brute-force approach outlined in the solution, we conclude that the next numerically balanced number greater than 300 is 333. While this method is straightforward, it is also clear that for a large number the number of iterations can become significant, which highlights the inefficiency for larger inputs.

Solution Implementation

1class Solution:
2    def nextBeautifulNumber(self, n: int) -> int:
3        # Define a function to check if a number is 'beautiful'.
4        # A number is beautiful if the frequency of each digit is equal to the digit itself.
5        def is_beautiful(num):
6            # Initialize a counter for each digit from 0 to 9.
7            frequency_counter = [0] * 10
8          
9            # Increment the counter for each digit found in the number.
10            for digit_char in str(num):
11                digit = int(digit_char)
12                frequency_counter[digit] += 1
13
14            # Check if the frequency of each digit is equal to the digit itself.
15            for digit_char in str(num):
16                digit = int(digit_char)
17                if frequency_counter[digit] != digit:
18                    return False
19            return True
20
21        # Iterate through numbers greater than n to find the next beautiful number.
22        for i in range(n + 1, 10**7):
23            if is_beautiful(i):
24                # If the number is beautiful, return it.
25                return i
26      
27        # If no beautiful number is found (which is highly improbable), return -1.
28        # This is a safeguard, and in practice, this return statement should not be reached.
29        return -1
30
1class Solution {
2
3    // Finds the next beautiful number that is greater than a given number `n`
4    public int nextBeautifulNumber(int n) {
5        // Start from the next integer value and check up to an upper limit
6        for (int i = n + 1; i < 10000000; ++i) {
7            // Utilize the check method to determine if the number is beautiful
8            if (isBeautiful(i)) {
9                // Return the first beautiful number found
10                return i;
11            }
12        }
13        // Return -1 if no beautiful number is found (should not occur with the given constraints)
14        return -1;
15    }
16
17    // Helper method to check if a number is beautiful
18    private boolean isBeautiful(int num) {
19        // Initialize a counter to store the frequency of each digit
20        int[] digitCounter = new int[10];
21      
22        // Convert the number to a character array
23        char[] chars = String.valueOf(num).toCharArray();
24      
25        // Increment the count for each digit found
26        for (char c : chars) {
27            digitCounter[c - '0']++;
28        }
29      
30        // Check if each digit appears exactly as many times as the digit itself
31        for (char c : chars) {
32            if (digitCounter[c - '0'] != c - '0') {
33                // If not, the number is not beautiful
34                return false;
35            }
36        }
37      
38        // If all digits match the criteria, the number is beautiful
39        return true;
40    }
41}
42
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find the next beautiful number greater than a given number n.
8    int nextBeautifulNumber(int n) {
9        // Loop starts from the next number after n and stops when it finds a beautiful number.
10        for (int i = n + 1; i < 10000000; ++i) {
11            // If i is a beautiful number, return it.
12            if (isBeautiful(i)) {
13                return i;
14            }
15        }
16        // Return -1 if no beautiful number is found (this won't happen given the problem constraints).
17        return -1;
18    }
19
20private:
21    // Helper function to check if a number is beautiful.
22    // A beautiful number has each digit appearing exactly d times where d is the actual digit.
23    bool isBeautiful(int num) {
24        // Convert the number to a string.
25        string numStr = to_string(num);
26      
27        // Initialize a counter for each digit (0-9).
28        vector<int> digitCounter(10, 0);
29      
30        // Increment the counter for each digit found in the number.
31        for (char digit : numStr) {
32            ++digitCounter[digit - '0'];
33        }
34      
35        // Check if the count of each digit matches its value.
36        for (char digit : numStr) {
37            if (digitCounter[digit - '0'] != digit - '0') {
38                // If any digit count doesn't match its value, the number isn't beautiful.
39                return false;
40            }
41        }
42      
43        // All digit counts match their values, so the number is beautiful.
44        return true;
45    }
46};
47
1function nextBeautifulNumber(n: number): number {
2    // Start checking numbers greater than the given number
3    for (let answer = n + 1; ; answer++) {
4        // Check if the current number is "beautiful"
5        if (isValid(answer)) {
6            // If it's a beautiful number, then return it as the answer
7            return answer;
8        }
9    }
10}
11
12function isValid(n: number): boolean {
13    // Initialize digit occurrence record with zeros
14    let digitFrequency = new Array(10).fill(0);
15  
16    // While there are still digits to process
17    while (n > 0) {
18        // Get the rightmost digit of the number
19        const currentDigit = n % 10;
20        // Increment the frequency of the currentDigit
21        digitFrequency[currentDigit]++;
22        // Remove the rightmost digit from the number
23        n = Math.floor(n / 10);
24    }
25  
26    // Check all digits from 0 to 9
27    for (let i = 0; i < 10; i++) {
28        // If a digit occurs and its frequency is not equal to the digit itself, it's not valid
29        if (digitFrequency[i] && digitFrequency[i] != i) return false;
30    }
31  
32    // If all conditions are met, return true
33    return true;
34}
35

Time and Space Complexity

Time Complexity

The function nextBeautifulNumber increments a number, starting from n + 1, and checks each number to see if it is a "beautiful" number as defined by the function check. The check function verifies if the number of times each digit appears is equal to the digit itself.

The time complexity of the check function is as follows:

  1. Converting a number to its string representation is O(log(num)), because the length of the string is proportional to the number of digits in the number.
  2. Counting the digits by using an array of size 10 (for each possible digit) is done in O(log(num)), where log(num) is the number of digits in num.
  3. Again, it iterates over each digit to verify if the number is beautiful, which is also O(log(num)).

Combining these steps, the function check alone is O(log(num)). However, we need to consider that it is called for each number starting from n + 1.

The loop can be considered to go on until the next beautiful number is found, which is the worst-case scenario since we do not know the distribution of beautiful numbers. If we say finding the next beautiful number from n has a maximum range of r, the total time complexity is O(r * log(r)).

The exact value of r is not straightforward to determine as it depends on the pattern distribution of beautiful numbers, but given the constraint that the for loop can go up to 10^7, in the worst case scenario r would be close to 10^7, making it O(7 * 10^7), which simplifies to O(10^7).

Space Complexity

The space complexity is primarily impacted by:

  1. The counter array which holds 10 integers, representing each digit, so it remains constant O(1).
  2. The string representation of the number being checked inside the loop, which has a space complexity of O(log(num)) for each number num.

Since the counter array is static and doesn't grow with the input, and the string representation of the current number is only stored temporarily for each check, the space complexity can be simplified to O(1) because the logarithmic space required for the string representation does not affect the overall space complexity which is dominated by the fixed size of the counter array.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More