2048. Next Greater Numerically Balanced Number

Description

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 <= 106

 

Solutions

Solution: Enumeration

• Time complexity: O(M-n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const nextBeautifulNumber = function (n) {
  let current = n + 1;

  const isBalanced = num => {
    const counts = new Array(10).fill(0);

    while (num) {
      const digit = num % 10;

      if (!digit) return false;

      counts[digit] += 1;
      num = Math.floor(num / 10);
    }

    for (let index = 1; index < 10; index++) {
      if (counts[index] && counts[index] !== index) return false;
    }

    return true;
  };

  while (!isBalanced(current)) {
    current += 1;
  }

  return current;
};