2048. Next Greater Numerically Balanced Number

2048. Next Greater Numerically Balanced Number

Difficulty: Medium

Topics: Hash Table, Math, Backtracking, Counting, Enumeration, Weekly Contest 264

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 <= 10⁶

Hint:

1. How far away can the next greater numerically balanced number be from n?


2. With the given constraints, what is the largest numerically balanced number?

Solution:

We need to find the smallest numerically balanced number strictly greater than the given integer n. A number is numerically balanced if for every digit d present in the number, it appears exactly d times.

Approach:

1. Start checking numbers from n + 1 onwards.


2. For each number, check if it is numerically balanced.


3. To check if a number is balanced:
   
   
   
   
   • Count the occurrences of each digit in the number.
   
   
   • Ensure that for every digit d that appears in the number, the count of d is exactly d. If any digit violates this condition, the number is not balanced.
   
   
   
   


4. The first number that satisfies this condition is returned as the result.

This method efficiently checks each subsequent number until the condition is met. Given the constraints (n ≤ 10^6), this approach is feasible as the next balanced number is typically not too far from n.

Let's implement this solution in PHP: 2048. Next Greater Numerically Balanced Number

<?php

/**

 * @param Integer $n

 * @return Integer

 */

function nextBeautifulNumber($n) {

    ...

    ...

    ...

    /**

     * go to ./solution.php

     */

}





/**

 * Check if a number is numerically balanced

 *

 * @param $num

 * @return bool

 */

function isBalanced($num) {

    ...

    ...

    ...

    /**

     * go to ./solution.php

     */

}



// Test cases

echo nextBeautifulNumber(1) . "\n";     // Output: 22

echo nextBeautifulNumber(1000) . "\n";  // Output: 1333

echo nextBeautifulNumber(3000) . "\n";  // Output: 3133

?>

Explanation:

1. 
   Initialization: We start by initializing candidate to n + 1, the first number to check.


2. 
   Checking Loop: We enter a loop that continues until a balanced number is found. For each candidate, we check if it is balanced using the helper function isBalanced.


3. 
   Balanced Check: The isBalanced function counts the occurrences of each digit in the number. It then checks if every digit that appears does so exactly as many times as its value. If any digit fails this check, the function returns false; otherwise, it returns true.


4. 
   Result: Once a balanced number is found, it is returned immediately.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn


• GitHub