# Convert Integer to the Sum of Two No-Zero Integers
**Difficulty:** EASY
[External](https://leetcode.com/problems/convert-integer-to-the-sum-of-two-no-zero-integers)
Canonical: https://scaleengineer.com/dsa/problems/convert-integer-to-the-sum-of-two-no-zero-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Hudson River Trading](https://scaleengineer.com/companies/hudson-river-trading)
---
## Problem
**No-Zero integer** is a positive integer that **does not contain any `0`** in its decimal representation.

Given an integer `n`, return _a list of two integers_ `[a, b]` _where_:

* `a` and `b` are **No-Zero integers**.
* `a + b = n`

The test cases are generated so 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:** Let a = 1 and b = 1.
Both a and b are no-zero integers, and a + b = 2 = n.

**Example 2:**

**Input:** n = 11
**Output:** [2,9]
**Explanation:** Let a = 2 and b = 9.
Both a and b are no-zero integers, and a + b = 11 = n.
Note that there are other valid answers as [8, 3] that can be accepted.

**Constraints:**

* `2 <= n <= 104`

# Approaches
## Brute Force with String Conversion
This approach uses a straightforward brute-force search. It iterates through all possible values for the first number, `a`, starting from 1. For each `a`, it calculates the required second number, `b`, such that `a + b = n`. The core of this method is a helper function that checks if a number contains the digit zero. In this version, the check is done by converting the numbers to strings and searching for the character '0'. While simple to implement, this method is less efficient due to the overhead of string manipulation.
**Time:** O(n * log n). The main loop runs `n-1` times. Inside the loop, converting a number `k` to a string and checking it takes time proportional to the number of its digits, which is `O(log k)`. The largest number checked is `n`, so the check is `O(log n)`. · **Space:** O(log n). The space is dominated by the string conversion. The length of the string representation of a number `k` is proportional to `log10(k)`. In the worst case, we check `n`, so the space is `O(log n)`.
**Pros:** The logic is very simple and easy to understand.; It is guaranteed to find a solution as per the problem statement.
**Cons:** The time complexity is linear with respect to `n`, making it less suitable for very large values of `n`.; String conversion and checking can be less performant than a purely mathematical approach due to the overhead of creating string objects.
### Explanation
The algorithm iterates through every possible integer `a` from `1` to `n-1`. For each `a`, it determines the corresponding integer `b` by the relation `b = n - a`. The next step is to validate if both `a` and `b` are No-Zero integers. This validation is performed by a helper function, `containsZero()`, which converts each number into a string and then checks for the presence of the character `'0'`. If `!containsZero(a)` and `!containsZero(b)` are both true, we have found our solution and can immediately return `[a, b]`. Given the problem's guarantee that at least one solution exists, this method is sure to terminate with a correct answer.

```java
class Solution {
    public int[] getNoZeroIntegers(int n) {
        for (int a = 1; a < n; a++) {
            int b = n - a;
            if (!containsZero(a) && !containsZero(b)) {
                return new int[]{a, b};
            }
        }
        return new int[]{}; // This line is unreachable given the problem constraints.
    }

    private boolean containsZero(int num) {
        return String.valueOf(num).contains("0");
    }
}
```
### Algorithm
1. Create a helper function `containsZero(int num)` that works as follows:
   - Convert the input number `num` to its string representation.
   - Check if the resulting string contains the character `'0'`. 
   - Return `true` if it does, `false` otherwise.
2. Start a loop for the first integer, `a`, from `1` up to `n - 1`.
3. Inside the loop, calculate the second integer, `b`, as `n - a`.
4. Call the `containsZero` helper function for both `a` and `b`.
5. If neither `a` nor `b` contains a zero, a valid pair has been found.
6. Return the pair `[a, b]`. Since a solution is guaranteed to exist, the loop will always find one.

## Brute Force with Mathematical Check
This approach is an optimized version of the brute-force method. The overall strategy is the same: iterate through possible values for `a` and check if both `a` and `b = n - a` are No-Zero integers. The key difference and improvement lie in how the No-Zero check is performed. Instead of converting numbers to strings, this method uses a more efficient mathematical technique involving modulo and division operations to inspect the digits of each number. This avoids the overhead associated with string manipulation and memory allocation, leading to better performance and lower memory usage.
**Time:** O(n * log n). The loop runs `n` times. The mathematical check for zeros on a number `k` takes `O(log k)` time, as the number of iterations depends on the number of digits. This makes it faster in practice than the string-based approach due to lower constant factors. · **Space:** O(1). This approach uses only a fixed number of variables for calculations, regardless of the input size `n`. No auxiliary data structures are needed.
**Pros:** More efficient in terms of both time and space compared to the string conversion method.; Maintains the simplicity and correctness of the brute-force approach.; Requires no extra space that scales with the input size.
**Cons:** The overall time complexity is still `O(n * log n)`, which might not be optimal for extremely large inputs, although it's perfectly fine for the given constraints.
### Explanation
The algorithm iterates from `a = 1` to `n-1`. For each `a`, `b` is calculated as `n - a`. The crucial part is the `containsZero(num)` helper function. This function efficiently checks for zero digits using arithmetic. It repeatedly examines the last digit of a number with `num % 10`. If this digit is `0`, the number is not a No-Zero integer. If it's not `0`, the last digit is removed by `num /= 10`, and the process continues until the number becomes `0`. If the loop finishes without ever finding a `0` digit, the number is a valid No-Zero integer. This check is performed for both `a` and `b`. The first pair `[a, b]` that passes the check for both numbers is returned.

```java
class Solution {
    public int[] getNoZeroIntegers(int n) {
        for (int a = 1; a < n; a++) {
            int b = n - a;
            if (!containsZero(a) && !containsZero(b)) {
                return new int[]{a, b};
            }
        }
        return new int[]{}; // This line is unreachable given the problem constraints.
    }

    private boolean containsZero(int num) {
        while (num > 0) {
            if (num % 10 == 0) {
                return true;
            }
            num /= 10;
        }
        return false;
    }
}
```
### Algorithm
1. Create a helper function `containsZero(int num)` that works as follows:
   - Use a `while` loop that continues as long as `num` is greater than 0.
   - In each iteration, get the last digit of `num` using the modulo operator (`num % 10`).
   - If the last digit is `0`, return `true` immediately.
   - Otherwise, remove the last digit by integer division (`num /= 10`).
   - If the loop completes without finding a `0`, return `false`.
2. Start a loop for the first integer, `a`, from `1` up to `n - 1`.
3. Inside the loop, calculate the second integer, `b`, as `n - a`.
4. Use the mathematical `containsZero` helper function to check both `a` and `b`.
5. If neither number contains a zero, return the pair `[a, b]`.

# Solutions
### Java

```java
class Solution {
public
  int[] getNoZeroIntegers(int n) {
    for (int a = 1;; ++a) {
      int b = n - a;
      if (!(a + "" + b).contains("0")) {
        return new int[]{a, b};
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> getNoZeroIntegers(int n) {
    for (int a = 1;; ++a) {
      int b = n - a;
      if ((to_string(a) + to_string(b)).find('0') == -1) {
        return {a, b};
      }
    }
  }
};

```

### Python

```python
class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]: for a in range(1, n): b = n - a if "0" not in str(a) + str(b): return [a, b]

```