Convert Integer to the Sum of Two No-Zero Integers - Solution & Explanation
Problem Statement
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:
aandbare 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
Approach Overview
Problem Overview: You are given an integer n. The task is to find two positive integers a and b such that a + b = n and neither number contains the digit 0. These are called no-zero integers. The problem mainly tests digit manipulation and simple search using math reasoning.
Approach 1: Iterative Checking Method (O(n log n) time, O(1) space)
Start with a = 1 and compute b = n - a. For each pair, check whether both numbers contain the digit 0. The digit check is done by repeatedly taking num % 10 and dividing by 10. If neither number contains zero, you found a valid pair and can return it immediately. In the worst case you may test many values of a, but each digit check only takes O(log n) time because the number of digits grows logarithmically. The algorithm uses constant extra memory since only a few integer variables are maintained.
This approach works because the constraints guarantee that at least one valid pair exists. The logic is straightforward and easy to implement in any language. It relies purely on integer arithmetic and simple iteration rather than additional data structures.
Approach 2: Randomized Shuffling Method (Expected O(log n) time, O(1) space)
Instead of scanning sequentially, randomly generate candidate values for a between 1 and n-1. Compute b = n - a and check whether both numbers contain no zero digits. If the pair fails the digit constraint, generate another random candidate and repeat. Because many integers do not contain the digit zero, a valid pair is typically found after only a few attempts.
The validation step is identical to the iterative method: repeatedly extract digits using modulus and division. The randomness reduces the expected number of trials, making the average runtime close to constant for typical values of n. The tradeoff is that runtime becomes probabilistic rather than deterministic.
Both strategies rely on the same core idea: verify digits directly instead of building strings or using additional structures. This keeps memory usage constant and the implementation simple. Problems like this commonly appear in basic math and number theory practice because they test comfort with digit operations.
Recommended for interviews: The iterative checking approach is what interviewers usually expect. It demonstrates clear reasoning, deterministic behavior, and clean digit validation logic. Randomized sampling can be discussed as an optimization idea, but deterministic iteration communicates stronger problem‑solving discipline in interviews.
Approach 1: Iterative Checking Method
This approach involves iterating from 1 to n-1 and checking if both the iterated number and the complement to n are no-zero integers. The solution stops once such a pair is found.
The function isNoZero checks if the number contains a '0'. The main logic then iterates through possible pairs, checking each until a valid pair is found.
Complexity
Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Randomized Shuffling Method
This approach uses a random shuffling of digits to attempt different combinations as a and b until a valid pair is found. While fun, it is generally less efficient than the iterative method.
This randomized approach in Python tries different random numbers, ensuring they are no-zero integers until a valid pair is found.
Code
Python
Complexity
Average Time Complexity: O(1) in the best case, O(n) or higher in the worst case due to randomness. Space Complexity: O(1).
Approach 3: 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].
The time complexity is O(n times log n), where n is the integer given in the problem. The space complexity is O(log n).
Approach 4: 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].
The time complexity is O(n times log n), where n is the integer given in the problem. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Checking Method | Time Complexity: O(n). Space Complexity: O(1). |
| Randomized Shuffling Method | Average Time Complexity: O(1) in the best case, O(n) or higher in the worst case due to randomness. Space Complexity: O(1). |
| Direct Enumeration | — |
| Direct Enumeration (Alternative Approach) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Checking Method | O(n log n) | O(1) | Deterministic solution with simple logic. Best for interviews and predictable runtime. |
| Randomized Shuffling Method | Expected O(log n) | O(1) | When random sampling is acceptable and you want faster average discovery of a valid pair. |
Video Solution
1317. Convert Integer to the Sum of Two No-Zero Integers | Leetcode Daily - Python • Leetcode Daily • 1,489 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Convert Integer to the Sum of Two No-Zero Integers easy or hard?
Convert Integer to the Sum of Two No-Zero Integers Python/Java solution
How to solve Convert Integer to the Sum of Two No-Zero Integers in O(n)?
What is the best approach for Convert Integer to the Sum of Two No-Zero Integers?
Is Convert Integer to the Sum of Two No-Zero Integers asked at Google/Amazon/Meta?
What data structure is used in Convert Integer to the Sum of Two No-Zero Integers?
What is the time complexity of Convert Integer to the Sum of Two No-Zero Integers?
Ready to solve this problem?
Practice Convert Integer to the Sum of Two No-Zero Integers with our built-in code editor and test cases.
Practice on FleetCode