How to Convert Integer to the Sum of Two No-Zero Integers?

  • 时间:2020-09-12 10:06:27
  • 分类:网络文摘
  • 阅读:100 次

Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

A and B are No-Zero integers.
A + B = n
It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

Example 1:
Input: n = 2
Output: [1,1]
Explanation: A = 1, B = 1. A + B = n and both A and B don’t contain any 0 in their decimal representation.
Example 2:

Input: n = 11
Output: [2,9]
Example 3:

Input: n = 10000
Output: [1,9999]
Example 4:

Input: n = 69
Output: [1,68]
Example 5:

Input: n = 1010
Output: [11,999]

Constraints:
2 <= n <= 10^4

Hints:
Loop through all elements from 1 to n.
Choose A = i and B = n – i then check if A and B are both No-Zero integers.

Bruteforce Algorithm to Convert an Integer to Two NonZero Sum

The bruteforce algorithm is intuitive solution that we can use to check the first integer range from 1 to n – 1, then we need to check both numbers if they contain zeros.

To check if a integer has zeros in it, one approach would be to convert it to string. For example, in C++, we can use std::to_string() to convert a integer to std::string. Alternatively, we can check the rightmost (least significant) digit and divide by ten repeatedly.

Below are the bruteforce implementations of C++, Python and Java respectively.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] getNoZeroIntegers(int n) {
        for (int i = 1; i < n; ++ i) {
            int a = i;
            int b = n - a;
            if (nozeros(a) && nozeros(b)) {
                return new int[]{a, b};
            }
        }
        return null;
    }
    
    private boolean nozeros(int x) {
        while (x > 0) {
            if (x % 10 == 0) return false;
            x /= 10;
        }
        return true;
    }
}
class Solution {
    public int[] getNoZeroIntegers(int n) {
        for (int i = 1; i < n; ++ i) {
            int a = i;
            int b = n - a;
            if (nozeros(a) && nozeros(b)) {
                return new int[]{a, b};
            }
        }
        return null;
    }
    
    private boolean nozeros(int x) {
        while (x > 0) {
            if (x % 10 == 0) return false;
            x /= 10;
        }
        return true;
    }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> getNoZeroIntegers(int n) {
        for (int i = 1; i < n; ++ i) {
            if (nonzeros(i) && nonzeros(n - i)) {
                return {i, n - i};
            }
        }
        return {};
    }
private:
    bool nonzeros(int n) {
        while (n > 0) {
            if (n % 10 == 0) return false;
            n /= 10;
        }
        return true;
    }
};
class Solution {
public:
    vector<int> getNoZeroIntegers(int n) {
        for (int i = 1; i < n; ++ i) {
            if (nonzeros(i) && nonzeros(n - i)) {
                return {i, n - i};
            }
        }
        return {};
    }
private:
    bool nonzeros(int n) {
        while (n > 0) {
            if (n % 10 == 0) return false;
            n /= 10;
        }
        return true;
    }
};

Python

1
2
3
4
5
6
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        a = 1
        while '0' in f'{a}{n-a}':
            a += 1
        return [a, n - a]
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        a = 1
        while '0' in f'{a}{n-a}':
            a += 1
        return [a, n - a]

The following is interesting as we are using the generator to yield the first (next) valid solution.

1
2
3
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        return next([a, n - a] for a in range(1, n) if not '0' in f'{a}{n - a}')
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        return next([a, n - a] for a in range(1, n) if not '0' in f'{a}{n - a}')

All the above implementations run at O(N) time and O(1) constant space.

We can also use two pointers starting at both ends towards each other, and the complexity will be the same.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
谷歌seo的内容素材和文章构思从哪里获取?(上篇)  seo专家告诉你,新网站怎么做网站优化  企业做Google SEO如何用内链优化来提高排名  建网站赚钱注意事项 别怪我没提醒你  自己建网站可以挣钱吗?做个人网站赚钱你必须要掌握的基础经验  网站赚钱 有时候就是那么简单  网上“复制”项目容易又免费 “粘贴”赚钱怎么那么简单  2020年网站赚钱应该怎么操作?  如果我们会做网站 有这个技能应该怎么赚钱?  美丽的厦门作文400字 
评论列表
添加评论