LeetCode 1317 - Convert Integer to the Sum of Two No-Zero Integers

The problem asks us to split a given integer n into two positive integers a and b such that: - a + b = n - Neither a nor b contains the digit 0 anywhere in their decimal representation Such integers are called No-Zero integers.

leetcodeeasymath

LeetCode Problem 1317

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem asks us to split a given integer n into two positive integers a and b such that:

  • a + b = n
  • Neither a nor b contains the digit 0 anywhere in their decimal representation

Such integers are called No-Zero integers.

The input is a single integer n, and the output should be a list or slice containing two valid integers. The problem guarantees that at least one valid answer always exists, so we do not need to handle impossible cases.

For example, if n = 11, one valid answer is [2, 9] because:

  • 2 contains no 0
  • 9 contains no 0
  • 2 + 9 = 11

However, [10, 1] would be invalid because 10 contains the digit 0.

The constraints are small:

  • 2 <= n <= 10^4

This immediately tells us that efficiency is not a major concern. Even a straightforward brute-force search over all possible splits of n is completely feasible because there are at most about 10,000 possibilities.

There are still a few important edge cases to think about:

  • Very small values like n = 2, where the only valid split is [1, 1]
  • Numbers that naturally produce zeros in one component, such as n = 101
  • Cases where one candidate contains multiple zeros, like 1000
  • Ensuring we correctly reject numbers such as 10, 20, or 101

The problem guarantee that a solution always exists simplifies the implementation because once we find a valid pair, we can immediately return it.

Approaches

Brute-Force Approach

The most direct solution is to try every possible split of n.

We iterate through all integers a from 1 to n - 1. For each value:

  • Compute b = n - a
  • Check whether a contains the digit 0
  • Check whether b contains the digit 0

If both numbers are valid No-Zero integers, we return the pair.

To check whether a number contains a zero, we can convert it to a string and search for the character '0'.

This approach is guaranteed to work because we examine every possible decomposition of n into two positive integers. Since the problem guarantees that a valid answer exists, we will eventually find one.

Because n is at most 10^4, this brute-force solution is already fast enough.

Key Insight

The key observation is that the search space is extremely small.

There is no need for advanced mathematics, dynamic programming, or greedy optimization. We only need an efficient way to test whether a number contains a zero digit.

The optimal practical solution is therefore still based on brute force, but implemented cleanly and efficiently:

  • Iterate through all candidate pairs
  • Use a helper function to validate No-Zero integers
  • Return immediately once a valid pair is found

This is optimal for the given constraints because the search finishes very quickly in practice.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * d) O(d) Tries every split and checks digits using string conversion
Optimal O(n * d) O(d) Same practical approach, efficient enough because constraints are small

Here, d represents the number of digits in the numbers being checked. Since n <= 10^4, d is at most 5.

Algorithm Walkthrough

  1. Create a helper function is_no_zero(num) that determines whether a number contains the digit 0.
  2. Inside the helper function, convert the integer to a string and check whether '0' exists in the string representation.
  3. Iterate through all possible first numbers a from 1 to n - 1.
  4. For each a, compute the second number as b = n - a.
  5. Check whether both a and b are No-Zero integers using the helper function.
  6. As soon as we find a valid pair, return [a, b].
  7. Since the problem guarantees at least one solution exists, the algorithm will always return before the loop finishes.

Why it works

The algorithm checks every possible way to write n as the sum of two positive integers. For each pair, it verifies the exact property required by the problem, namely that neither number contains the digit 0. Because every possible pair is examined, the first valid pair found must be a correct answer.

Python Solution

from typing import List

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        def is_no_zero(num: int) -> bool:
            return '0' not in str(num)

        for a in range(1, n):
            b = n - a

            if is_no_zero(a) and is_no_zero(b):
                return [a, b]

        return []

The implementation starts by defining a helper function called is_no_zero. This function converts the number into a string and checks whether the character '0' appears anywhere in it. If not, the number satisfies the No-Zero condition.

The main loop iterates through all possible values of a from 1 to n - 1. For each candidate, we compute b so that a + b = n.

We then validate both numbers using the helper function. The moment we find a valid pair, we return it immediately. Because the problem guarantees a solution exists, the fallback return [] statement is never reached during valid execution, but it keeps the function syntactically complete.

Go Solution

package main

import "strconv"

func getNoZeroIntegers(n int) []int {
	isNoZero := func(num int) bool {
		s := strconv.Itoa(num)

		for _, ch := range s {
			if ch == '0' {
				return false
			}
		}

		return true
	}

	for a := 1; a < n; a++ {
		b := n - a

		if isNoZero(a) && isNoZero(b) {
			return []int{a, b}
		}
	}

	return []int{}
}

The Go solution follows the exact same logic as the Python implementation.

One difference is that Go does not have Python's convenient '0' not in str(num) syntax, so we explicitly iterate through the string representation of the number and check each character.

The function returns a slice of integers. Since the problem guarantees a solution exists, the empty slice at the end is only included for completeness.

Integer overflow is not a concern because the maximum value is only 10^4.

Worked Examples

Example 1

Input:

n = 2

We try all possible splits.

a b = n - a a contains 0? b contains 0? Valid?
1 1 No No Yes

The algorithm immediately returns:

[1, 1]

Example 2

Input:

n = 11

Step-by-step execution:

a b = n - a a contains 0? b contains 0? Valid?
1 10 No Yes No
2 9 No No Yes

The algorithm returns:

[2, 9]

Complexity Analysis

Measure Complexity Explanation
Time O(n * d) We may check up to n pairs, and each digit check costs O(d)
Space O(d) String conversion uses space proportional to the number of digits

The number of digits is very small because n <= 10^4, so in practice the solution runs extremely quickly. Even in the worst case, we perform only a few thousand checks.

Test Cases

from typing import List

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        def is_no_zero(num: int) -> bool:
            return '0' not in str(num)

        for a in range(1, n):
            b = n - a

            if is_no_zero(a) and is_no_zero(b):
                return [a, b]

def valid_pair(n: int, result: List[int]) -> bool:
    a, b = result
    return (
        a + b == n and
        '0' not in str(a) and
        '0' not in str(b)
    )

solution = Solution()

# Provided example: smallest valid input
assert valid_pair(2, solution.getNoZeroIntegers(2))

# Provided example with multiple valid answers
assert valid_pair(11, solution.getNoZeroIntegers(11))

# Number containing zero internally
assert valid_pair(101, solution.getNoZeroIntegers(101))

# Power of ten
assert valid_pair(1000, solution.getNoZeroIntegers(1000))

# Small odd number
assert valid_pair(19, solution.getNoZeroIntegers(19))

# Small even number
assert valid_pair(20, solution.getNoZeroIntegers(20))

# Maximum constraint
assert valid_pair(10000, solution.getNoZeroIntegers(10000))

# Case where first few splits fail
assert valid_pair(109, solution.getNoZeroIntegers(109))

# Consecutive zeros in target
assert valid_pair(1001, solution.getNoZeroIntegers(1001))

# Random mid-sized value
assert valid_pair(5678, solution.getNoZeroIntegers(5678))
Test Why
n = 2 Smallest possible input
n = 11 Standard example with multiple solutions
n = 101 Tests handling of zeros inside numbers
n = 1000 Tests powers of ten
n = 19 Small odd value
n = 20 Small even value
n = 10000 Maximum constraint
n = 109 Early candidate pairs contain zeros
n = 1001 Multiple zeros in target number
n = 5678 General mid-sized input

Edge Cases

One important edge case is the minimum input value, n = 2. There is only one possible split, [1, 1]. A buggy implementation might incorrectly start iterating from 0, which would violate the requirement that both integers must be positive. Our implementation starts from 1, so it handles this correctly.

Another important case involves numbers containing zeros, such as n = 101. Many candidate pairs will include numbers like 10, 20, or 100, which are invalid. The helper function explicitly checks every digit through string conversion, so such numbers are correctly rejected.

A third important edge case is large powers of ten such as 1000 or 10000. These numbers naturally create many invalid decompositions because zeros appear frequently in decimal representations. The brute-force search still works efficiently because the search space is small, and the algorithm simply skips invalid pairs until it finds a valid one.

A subtle edge case is when the first several candidate pairs are invalid. For example, with n = 11, the pair (1, 10) fails because 10 contains a zero. The algorithm must continue searching instead of stopping after the first failure. Our loop continues until a valid pair is found.