Watch 10 video solutions for Convert Integer to the Sum of Two No-Zero Integers, a easy level problem involving Math. This walkthrough by Leetcode Daily has 1,256 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 = nThe 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 <= 104Problem 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 | 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. |