Question

2417. 最近的公平整数

English Version

题目描述

给定一个 正整数 n。

如果一个整数 k 中的 偶数 位数与 奇数 位数相等，那么我们称 k 为公平整数。

返回 _大于或等于 _n_ 的 最小 的公平整数。_

 

示例 1:

输入: n = 2
输出: 10
解释: 大于等于 2 的最小的公平整数是 10。
10是公平整数，因为它的偶数和奇数个数相等 (一个奇数和一个偶数)。

示例 2:

输入: n = 403
输出: 1001
解释: 大于或等于 403 的最小的公平整数是 1001。
1001 是公平整数，因为它有相等数量的偶数和奇数 (两个奇数和两个偶数)。

 

提示:

• 1 <= n <= 109

解法

方法一：分类讨论

我们记 $n$ 的位数为 $k$，奇数位数、偶数位数分别为 $a$ 和 $b$。

• 若 $a=b$，则 $n$ 本身就是 fair 的，直接返回 $n$ 即可；
• 否则，若 $k$ 为奇数，那么我们找到 $k+1$ 位的最小 fair 数即可，形如 10000111；若 $k$ 为偶数，我们直接暴力递归 closestFair(n+1) 即可。

时间复杂度 $O(\sqrt{n} \times \log_{10} n)$。

class Solution:
  def closestFair(self, n: int) -> int:
    a = b = k = 0
    t = n
    while t:
      if (t % 10) & 1:
        a += 1
      else:
        b += 1
      t //= 10
      k += 1
    if k & 1:
      x = 10**k
      y = int('1' * (k >> 1) or '0')
      return x + y
    if a == b:
      return n
    return self.closestFair(n + 1)

class Solution {
  public int closestFair(int n) {
    int a = 0, b = 0;
    int k = 0, t = n;
    while (t > 0) {
      if ((t % 10) % 2 == 1) {
        ++a;
      } else {
        ++b;
      }
      t /= 10;
      ++k;
    }
    if (k % 2 == 1) {
      int x = (int) Math.pow(10, k);
      int y = 0;
      for (int i = 0; i < k >> 1; ++i) {
        y = y * 10 + 1;
      }
      return x + y;
    }
    if (a == b) {
      return n;
    }
    return closestFair(n + 1);
  }
}

class Solution {
public:
  int closestFair(int n) {
    int a = 0, b = 0;
    int t = n, k = 0;
    while (t) {
      if ((t % 10) & 1) {
        ++a;
      } else {
        ++b;
      }
      ++k;
      t /= 10;
    }
    if (a == b) {
      return n;
    }
    if (k % 2 == 1) {
      int x = pow(10, k);
      int y = 0;
      for (int i = 0; i < k >> 1; ++i) {
        y = y * 10 + 1;
      }
      return x + y;
    }
    return closestFair(n + 1);
  }
};

func closestFair(n int) int {
  a, b := 0, 0
  t, k := n, 0
  for t > 0 {
    if (t%10)%2 == 1 {
      a++
    } else {
      b++
    }
    k++
    t /= 10
  }
  if a == b {
    return n
  }
  if k%2 == 1 {
    x := int(math.Pow(10, float64(k)))
    y := 0
    for i := 0; i < k>>1; i++ {
      y = y*10 + 1
    }
    return x + y
  }
  return closestFair(n + 1)
}