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

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