Convert Integer to the Sum of Two No-Zero Integers
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward brute-force search. It iterates through all possible values for the first number, a, starting from 1. For each a, it calculates the required second number, b, such that a + b = n. The core of this method is a helper function that checks if a number contains the digit zero. In this version, the check is done by converting the numbers to strings and searching for the character '0'. While simple to implement, this method is less efficient due to the overhead of string manipulation.
Algorithm
- Create a helper function
containsZero(int num)that works as follows:- Convert the input number
numto its string representation. - Check if the resulting string contains the character
'0'. - Return
trueif it does,falseotherwise.
- Convert the input number
- Start a loop for the first integer,
a, from1up ton - 1. - Inside the loop, calculate the second integer,
b, asn - a. - Call the
containsZerohelper function for bothaandb. - If neither
anorbcontains a zero, a valid pair has been found. - Return the pair
[a, b]. Since a solution is guaranteed to exist, the loop will always find one.
Walkthrough
The algorithm iterates through every possible integer a from 1 to n-1. For each a, it determines the corresponding integer b by the relation b = n - a. The next step is to validate if both a and b are No-Zero integers. This validation is performed by a helper function, containsZero(), which converts each number into a string and then checks for the presence of the character '0'. If !containsZero(a) and !containsZero(b) are both true, we have found our solution and can immediately return [a, b]. Given the problem's guarantee that at least one solution exists, this method is sure to terminate with a correct answer.
class Solution { public int[] getNoZeroIntegers(int n) { for (int a = 1; a < n; a++) { int b = n - a; if (!containsZero(a) && !containsZero(b)) { return new int[]{a, b}; } } return new int[]{}; // This line is unreachable given the problem constraints. } private boolean containsZero(int num) { return String.valueOf(num).contains("0"); }}Complexity
Time
O(n * log n). The main loop runs `n-1` times. Inside the loop, converting a number `k` to a string and checking it takes time proportional to the number of its digits, which is `O(log k)`. The largest number checked is `n`, so the check is `O(log n)`.
Space
O(log n). The space is dominated by the string conversion. The length of the string representation of a number `k` is proportional to `log10(k)`. In the worst case, we check `n`, so the space is `O(log n)`.
Trade-offs
Pros
The logic is very simple and easy to understand.
It is guaranteed to find a solution as per the problem statement.
Cons
The time complexity is linear with respect to
n, making it less suitable for very large values ofn.String conversion and checking can be less performant than a purely mathematical approach due to the overhead of creating string objects.
This approach is an optimized version of the brute-force method. The overall strategy is the same: iterate through possible values for a and check if both a and b = n - a are No-Zero integers. The key difference and improvement lie in how the No-Zero check is performed. Instead of converting numbers to strings, this method uses a more efficient mathematical technique involving modulo and division operations to inspect the digits of each number. This avoids the overhead associated with string manipulation and memory allocation, leading to better performance and lower memory usage.
Algorithm
- Create a helper function
containsZero(int num)that works as follows:- Use a
whileloop that continues as long asnumis greater than 0. - In each iteration, get the last digit of
numusing the modulo operator (num % 10). - If the last digit is
0, returntrueimmediately. - Otherwise, remove the last digit by integer division (
num /= 10). - If the loop completes without finding a
0, returnfalse.
- Use a
- Start a loop for the first integer,
a, from1up ton - 1. - Inside the loop, calculate the second integer,
b, asn - a. - Use the mathematical
containsZerohelper function to check bothaandb. - If neither number contains a zero, return the pair
[a, b].
Walkthrough
The algorithm iterates from a = 1 to n-1. For each a, b is calculated as n - a. The crucial part is the containsZero(num) helper function. This function efficiently checks for zero digits using arithmetic. It repeatedly examines the last digit of a number with num % 10. If this digit is 0, the number is not a No-Zero integer. If it's not 0, the last digit is removed by num /= 10, and the process continues until the number becomes 0. If the loop finishes without ever finding a 0 digit, the number is a valid No-Zero integer. This check is performed for both a and b. The first pair [a, b] that passes the check for both numbers is returned.
class Solution { public int[] getNoZeroIntegers(int n) { for (int a = 1; a < n; a++) { int b = n - a; if (!containsZero(a) && !containsZero(b)) { return new int[]{a, b}; } } return new int[]{}; // This line is unreachable given the problem constraints. } private boolean containsZero(int num) { while (num > 0) { if (num % 10 == 0) { return true; } num /= 10; } return false; }}Complexity
Time
O(n * log n). The loop runs `n` times. The mathematical check for zeros on a number `k` takes `O(log k)` time, as the number of iterations depends on the number of digits. This makes it faster in practice than the string-based approach due to lower constant factors.
Space
O(1). This approach uses only a fixed number of variables for calculations, regardless of the input size `n`. No auxiliary data structures are needed.
Trade-offs
Pros
More efficient in terms of both time and space compared to the string conversion method.
Maintains the simplicity and correctness of the brute-force approach.
Requires no extra space that scales with the input size.
Cons
The overall time complexity is still
O(n * log n), which might not be optimal for extremely large inputs, although it's perfectly fine for the given constraints.
Solutions
Solution
class Solution {public int[] getNoZeroIntegers(int n) { for (int a = 1;; ++a) { int b = n - a; if (!(a + "" + b).contains("0")) { return new int[]{a, b}; } } }}class Solution {public: vector<int> getNoZeroIntegers(int n) { for (int a = 1;; ++a) { int b = n - a; if ((to_string(a) + to_string(b)).find('0') == -1) { return {a, b}; } } }};class Solution: def getNoZeroIntegers(self, n: int) -> List[int]: for a in range(1, n): b = n - a if "0" not in str(a) + str(b): return [a, b]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.