Question

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 1: Enumeration

We note that the range of $n$ in the problem is $[0, 10^6]$, and one of the balanced numbers greater than $10^6$ is $1224444$. Therefore, we directly enumerate $x \in [n + 1, ..]$ and then judge whether $x$ is a balanced number. The enumerated $x$ will definitely not exceed $1224444$.

The time complexity is $O(M - n)$, where $M = 1224444$. The space complexity is $O(1)$.

class Solution:
  def nextBeautifulNumber(self, n: int) -> int:
    for x in count(n + 1):
      y = x
      cnt = [0] * 10
      while y:
        y, v = divmod(y, 10)
        cnt[v] += 1
      if all(v == 0 or i == v for i, v in enumerate(cnt)):
        return x

class Solution {
  public int nextBeautifulNumber(int n) {
    for (int x = n + 1;; ++x) {
      int[] cnt = new int[10];
      for (int y = x; y > 0; y /= 10) {
        ++cnt[y % 10];
      }
      boolean ok = true;
      for (int y = x; y > 0; y /= 10) {
        if (y % 10 != cnt[y % 10]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        return x;
      }
    }
  }
}

class Solution {
public:
  int nextBeautifulNumber(int n) {
    for (int x = n + 1;; ++x) {
      int cnt[10]{};
      for (int y = x; y > 0; y /= 10) {
        ++cnt[y % 10];
      }
      bool ok = true;
      for (int y = x; y > 0; y /= 10) {
        if (y % 10 != cnt[y % 10]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        return x;
      }
    }
  }
};

func nextBeautifulNumber(n int) int {
  for x := n + 1; ; x++ {
    cnt := [10]int{}
    for y := x; y > 0; y /= 10 {
      cnt[y%10]++
    }
    ok := true
    for y := x; y > 0; y /= 10 {
      if y%10 != cnt[y%10] {
        ok = false
        break
      }
    }
    if ok {
      return x
    }
  }
}

function nextBeautifulNumber(n: number): number {
  for (let x = n + 1; ; ++x) {
    const cnt: number[] = Array(10).fill(0);
    for (let y = x; y > 0; y = (y / 10) | 0) {
      cnt[y % 10]++;
    }
    let ok = true;
    for (let i = 0; i < 10; ++i) {
      if (cnt[i] && cnt[i] !== i) {
        ok = false;
        break;
      }
    }
    if (ok) {
      return x;
    }
  }
}