#1317

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Convert Integer to the Sum of Two No-Zero Integers

Find two positive integers whose sum equals n and neither contains the digit zero, using a direct math-driven approach.

Problem Statement

Given a positive integer n, find two positive integers a and b such that a + b = n and both a and b contain no zero in their decimal representation. A No-Zero integer is defined as a number without any digit equal to 0.

Return any valid pair [a, b] that satisfies the conditions. The input guarantees at least one solution exists, and multiple correct answers are acceptable.

Examples

Example 1

Input: n = 2

Output: [1,1]

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]

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

Solution Approach

Iterate Through Possible Pairs

Loop from 1 to n-1, setting a = i and b = n - i. For each pair, check if both numbers contain zero digits. Return immediately once a valid pair is found. This approach leverages the math-driven pattern and ensures the simplest working solution is detected.

Digit Check Function

Define a helper function to verify whether a number contains any zero digit. Convert the number to a string and scan each character. This avoids subtle errors in arithmetic-only checks and prevents accidentally including numbers with zeros.

Early Exit Optimization

Since the input guarantees at least one solution, the iteration can stop at the first valid pair. This reduces unnecessary computation and aligns with the pattern where the first feasible math-driven combination is sufficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * d) where d is the number of digits in each candidate because each number requires a digit scan. Space complexity is O(1) aside from the output, since only a few variables are stored.

What Interviewers Usually Probe

Expect a simple iteration solution that respects the no-zero constraint.
Check if candidates are properly validated for zero digits, not just summed to n.
Look for early exit and helper function separation as signs of clear implementation.

Common Pitfalls or Variants

Common pitfalls

Returning a pair without checking zero digits can lead to wrong solutions.
Assuming only one solution exists may cause unnecessary complexity.
Checking digits incorrectly or using arithmetic tricks can fail on numbers containing 0s internally.

Follow-up variants

Find three positive integers summing to n, all without zero digits.
Count all pairs of no-zero integers that sum to n.
Modify to exclude numbers containing a specific forbidden digit other than zero.

FAQ

What is a No-Zero integer in this problem?

A No-Zero integer is any positive number whose decimal representation does not contain the digit 0.

Can multiple valid pairs be returned for n?

Yes, any pair [a, b] where a + b = n and both contain no zeros is accepted.

What is the recommended approach for Convert Integer to the Sum of Two No-Zero Integers?

Use a math-driven strategy: loop from 1 to n, check each candidate pair for zero digits, and return the first valid combination.

What is the time complexity of the solution?

It is O(n * d), where d is the number of digits in the candidate numbers due to digit scanning.

How do I check if a number contains zero efficiently?

Convert the number to a string and verify that no character equals '0'; this ensures correct validation for all digits.

terminal

Solution

Solution 1: Direct Enumeration

Starting from $1$, we enumerate $a$, then $b = n - a$. For each $a$ and $b$, we convert them to strings and concatenate them, then check if they contain the character '0'. If they do not contain '0', we have found the answer and return $[a, b]$.

1

2

3

4

5

6

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        for a in count(1):
            b = n - a
            if "0" not in f"{a}{b}":
                return [a, b]

Solution 2: Direct Enumeration (Alternative Approach)

In Solution 1, we converted $a$ and $b$ into strings and concatenated them, then checked if they contained the character '0'. Here, we can use a function $f(x)$ to check whether $x$ contains the character '0', and then directly enumerate $a$, checking whether both $a$ and $b = n - a$ do not contain the character '0'. If they do not, we have found the answer and return $[a, b]$.

1

2

3

4

5

6

class Solution:
    def getNoZeroIntegers(self, n: int) -> List[int]:
        for a in count(1):
            b = n - a
            if "0" not in f"{a}{b}":
                return [a, b]

Continue Practicing

#1323 maximum 69 number #1307 verbal arithmetic puzzle #1304 find n unique integers sum up to zero