跳转至

2417. 最近的公平整数 🔒

题目描述

给定一个 正整数 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)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)
}

评论