Difficulty: Easy | Acceptance: 59.20% | Paid: No Topics: Math
Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.
Return a list of two integers [A, B] where:
A and B are No-Zero integers. A + B = n It’s guaranteed that there is at least one valid solution. Try to optimize your time and space complexity.
- Examples
- Constraints
- Brute Force
- Optimized Iteration
- Precompute No-Zero Numbers
Examples
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 <= 10⁴
Brute Force
Intuition Iterate through all possible values of a from 1 to n-1 and check if both a and b = n - a don’t contain any zero digits.
Steps
- Define a helper function to check if a number contains any zero digit
- Iterate through all possible values of a from 1 to n-1
- For each a, calculate b = n - a
- Check if both a and b don’t contain zeros
- Return the first valid pair found
class Solution:
def getNoZeroIntegers(self, n: int) -> List[int]:
def has_zero(x: int) -> bool:
while x > 0:
if x % 10 == 0:
return True
x //= 10
return False
for a in range(1, n):
b = n - a
if not has_zero(a) and not has_zero(b):
return [a, b]
return []Complexity
- Time: O(n × log n) - We iterate through n values and each check takes O(log n) time
- Space: O(1) - Only using constant extra space
- Notes: Simple and straightforward approach that works well for the given constraints
Optimized Iteration
Intuition Skip numbers that contain zeros while iterating to reduce unnecessary checks, improving efficiency.
Steps
- Define helper functions to check for zeros and find the next number without zeros
- Start from a = 1 and find the next number without zeros
- Calculate b = n - a and check if it also has no zeros
- If valid, return the pair; otherwise, increment a and continue
class Solution:
def getNoZeroIntegers(self, n: int) -> List[int]:
def has_zero(x: int) -> bool:
while x > 0:
if x % 10 == 0:
return True
x //= 10
return False
def next_no_zero(x: int) -> int:
while has_zero(x):
x += 1
return x
a = 1
while a < n:
a = next_no_zero(a)
b = n - a
if b > 0 and not has_zero(b):
return [a, b]
a += 1
return []Complexity
- Time: O(n × log n) - Same worst case as brute force but with better average case
- Space: O(1) - Only using constant extra space
- Notes: Skips unnecessary checks for numbers containing zeros, improving average performance
Precompute No-Zero Numbers
Intuition Precompute all numbers without zeros up to n, then iterate through them to find a valid pair.
Steps
- Define a helper function to check if a number contains any zero digit
- Precompute all numbers from 1 to n-1 that don’t contain zeros
- Iterate through the precomputed list and check if the complement also has no zeros
- Return the first valid pair found
class Solution:
def getNoZeroIntegers(self, n: int) -> List[int]:
def has_zero(x: int) -> bool:
while x > 0:
if x % 10 == 0:
return True
x //= 10
return False
no_zero = [i for i in range(1, n) if not has_zero(i)]
for a in no_zero:
b = n - a
if b > 0 and not has_zero(b):
return [a, b]
return []Complexity
- Time: O(n × log n) - Precomputation takes O(n × log n) time
- Space: O(n) - Storing all no-zero numbers up to n
- Notes: Uses extra space for precomputation but can be useful if multiple queries need to be processed