题目描述

无零整数是十进制表示中 不含任何 0 的正整数。

给你一个整数 n，请你返回一个由两个整数组成的列表 [A, B]，满足：

• A 和 B 都是无零整数
• A + B = n

题目数据保证至少有一个有效的解决方案。

如果存在多个有效解决方案，你可以返回其中任意一个。

样例

输入：n = 2
输出：[1,1]
解释：A = 1, B = 1. A + B = n 并且 A 和 B 的十进制表示形式都不包含任何 0 。

输入：n = 11
输出：[2,9]

输入：n = 10000
输出：[1,9999]

输入：n = 69
输出：[1,68]

输入：n = 1010
输出：[11,999]

限制

• 2 <= n <= 10^4

算法

(暴力枚举) $O(n \log n)$

1. 从 1 开始暴力枚举 A，检查 A 和 n - A 是否都是非零整数。

时间复杂度

• 最多枚举 $O(n)$ 个数字，每个数字需要 $O(\log n)$ 的时间检查，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 只需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool check(int x) {
        while (x) {
            if (x % 10 == 0)
                return false;
            x /= 10;
        }

        return true;
    }

    vector<int> getNoZeroIntegers(int n) {
        for (int i = 1; i <= n / 2; i++)
            if (check(i) && check(n - i))
                return {i, n - i};
        return {};
    }
};