README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/2400-2499/2417.Closest%20Fair%20Integer/README.md	数学 枚举

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)$。

Python3

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)

Java

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);
    }
}

C++

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);
    }
};

Go

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)
}