Convert Integer to the Sum of Two No-Zero Integers solution and explanation
Google
9 more videos on this problem
1317. Convert Integer to the Sum of Two No-Zero Integers | Leetcode Daily - PythonLeetcode Daily · 2:41 · 1K views
Convert Integer to the Sum of Two No Zero Integers | Leetcode 1317Techdose · 19:09 · 726 views
Leetcode 1317: Convert Integer to the Sum of Two No-Zero IntegersAlgorithms Casts · 9:03 · 652 views
1317. Convert Integer to the Sum of Two No-Zero Integers || leetcode || easy question || c++code Explainer · 3:16 · 441 views
LeetCode 1317 🔥 Convert Integer to the Sum of Two No-Zero Integers | Daily Challenge | 2 Approaches Study Placement · 8:49 · 267 views
Convert Integer to the Sum of Two No Zero Integers | LeetCode 1317 - Python (2 Solutions)impoldev · 5:30 · 230 views
Convert Integer to the Sum of Two No-Zero Integers | LeetCode 1317 | Beginner Must TrySanyam IIT Guwahati · 6:00 · 199 views
Convert Integer to the Sum of Two No Zero Integers | LeetCode 1317 | Math EasyCode Harmony · 11:18 · 195 views
Convert Integer to the Sum of Two No Zero Integers | Leetcode 1317 (Easy) | Codeminttcodemintt · 6:41 · 170 views
Leetcode 1317. Convert Integer to the Sum of Two No-Zero Integers PythonTechZoo · 3:00 · 169 views
The problem
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.
def is_no_zero(num):
return '0' not in str(num)
class Solution:
def get_no_zero_integers(self, n: int):
for a in range(1, n):
b = n - a
if is_no_zero(a) and is_no_zero(b):
return [a, b]
sol = Solution()
n = 11
print(sol.get_no_zero_integers(n))class Solution {
private boolean isNoZero(int num) {
while (num > 0) {
if (num % 10 == 0) return false;
num /= 10;
}
return true;
}
public int[] getNoZeroIntegers(int n) {
for (int i = 1; i < n; i++) {
if (isNoZero(i) && isNoZero(n - i)) {
return new int[]{i, n - i};
}
}
return new int[]{0, 0}; // Placeholder, should never happen
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 11;
int[] result = sol.getNoZeroIntegers(n);
System.out.println("[" + result[0] + ", " + result[1] + "]");
}
}#include <iostream>
using namespace std;
bool isNoZero(int num) {
while (num) {
if (num % 10 == 0) return false;
num /= 10;
}
return true;
}
pair<int, int> getNoZeroIntegers(int n) {
for (int i = 1; i < n; ++i) {
if (isNoZero(i) && isNoZero(n - i)) {
return {i, n - i};
}
}
return {0, 0}; // Placeholder, should never happen
}
int main() {
int n = 11;
auto result = getNoZeroIntegers(n);
cout << "[" << result.first << ", " << result.second << "]" << endl;
return 0;
}function isNoZero(num) {
return !num.toString().includes('0');
}
function getNoZeroIntegers(n) {
for (let i = 1; i < n; i++) {
if (isNoZero(i) && isNoZero(n - i)) {
return [i, n - i];
}
}
}
const n = 11;
console.log(getNoZeroIntegers(n));#include <stdio.h>
#include <stdbool.h>
bool isNoZero(int num) {
while (num) {
if (num % 10 == 0) return false;
num /= 10;
}
return true;
}
void getNoZeroIntegers(int n, int *a, int *b) {
for (int i = 1; i < n; ++i) {
if (isNoZero(i) && isNoZero(n - i)) {
*a = i;
*b = n - i;
return;
}
}
}
int main() {
int a, b, n = 11;
getNoZeroIntegers(n, &a, &b);
printf("[%d, %d]\n", a, b);
return 0;
}using System;
public class Solution {
private bool IsNoZero(int num) {
while (num > 0) {
if (num % 10 == 0) return false;
num /= 10;
}
return true;
}
public int[] GetNoZeroIntegers(int n) {
for (int i = 1; i < n; i++) {
if (IsNoZero(i) && IsNoZero(n - i)) {
return new int[] { i, n - i };
}
}
return new int[] { 0, 0 }; // Placeholder, should never happen
}
public static void Main(string[] args) {
Solution sol = new Solution();
int n = 11;
int[] result = sol.GetNoZeroIntegers(n);
Console.WriteLine("[{0}, {1}]", result[0], result[1]);
}
}The Python solution is straightforward, using a function to check for no-zero condition and iterating to find a valid pair.
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.
import random
def is_no_zero(num):
return '0' not in str(num)
class Solution:
def get_no_zero_integers(self, n: int):
while True:
a = random.randint(1, n-1)
b = n - a
if is_no_zero(a) and is_no_zero(b):
return [a, b]
sol = Solution()
n = 11
print(sol.get_no_zero_integers(n))This randomized approach in Python tries different random numbers, ensuring they are no-zero integers until a valid pair is found.
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).
function getNoZeroIntegers(n: number): number[] {
for (let a = 1; ; ++a) {
const b = n - a;
if (!`${a}${b}`.includes('0')) {
return [a, b];
}
}
}func getNoZeroIntegers(n int) []int {
for a := 1; ; a++ {
b := n - a
if !strings.Contains(strconv.Itoa(a)+strconv.Itoa(b), "0") {
return []int{a, b}
}
}
}impl Solution {
pub fn get_no_zero_integers(n: i32) -> Vec<i32> {
for a in 1..n {
let b = n - a;
if !a.to_string().contains('0') && !b.to_string().contains('0') {
return vec![a, b];
}
}
vec![]
}
}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).
function getNoZeroIntegers(n: number): number[] {
const f = (x: number): boolean => {
for (; x; x = (x / 10) | 0) {
if (x % 10 === 0) {
return false;
}
}
return true;
};
for (let a = 1; ; ++a) {
const b = n - a;
if (f(a) && f(b)) {
return [a, b];
}
}
}func getNoZeroIntegers(n int) []int {
f := func(x int) bool {
for ; x > 0; x /= 10 {
if x%10 == 0 {
return false
}
}
return true
}
for a := 1; ; a++ {
b := n - a
if f(a) && f(b) {
return []int{a, b}
}
}
}impl Solution {
pub fn get_no_zero_integers(n: i32) -> Vec<i32> {
fn f(mut x: i32) -> bool {
while x > 0 {
if x % 10 == 0 {
return false;
}
x /= 10;
}
true
}
for a in 1..n {
let b = n - a;
if f(a) && f(b) {
return vec![a, b];
}
}
vec![]
}
}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) | – |
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. |
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 is classified as an Easy problem. The challenge lies in recognizing that you can simply iterate candidate pairs and validate digits. No advanced algorithms or data structures are required.
Convert Integer to the Sum of Two No-Zero Integers Python/Java solution
The typical Python or Java implementation loops through possible values of a, calculates b = n − a, and runs a helper function that checks whether a number contains the digit 0. The first valid pair is returned. The algorithm runs in O(n log n) time and constant space across languages.
How to solve Convert Integer to the Sum of Two No-Zero Integers in O(n)?
You iterate through possible values of a from 1 to n−1 and compute b = n − a. For each pair, check digits using modulus and division to ensure neither number contains 0. The iteration is linear while each check processes digits, resulting in O(n log n) time overall with constant extra space.
What is the best approach for Convert Integer to the Sum of Two No-Zero Integers?
The iterative checking approach is the most reliable solution. Iterate a candidate value a from 1 to n−1, compute b = n − a, and verify that neither number contains the digit 0. Each digit check takes O(log n) time, giving overall O(n log n) time with O(1) space. This deterministic method is simple and commonly expected in coding interviews.
Is Convert Integer to the Sum of Two No-Zero Integers asked at Google/Amazon/Meta?
This problem is categorized as an easy math problem and appears in practice sets used for companies like Google and Amazon. It is more common in online assessments and early interview rounds where candidates are evaluated on basic number manipulation and clean implementation.
What data structure is used in Convert Integer to the Sum of Two No-Zero Integers?
No complex data structures are required. The solution relies on basic integer arithmetic and digit extraction using modulus (%) and division operations. This keeps the algorithm O(1) in space and focused on math-based validation.
What is the time complexity of Convert Integer to the Sum of Two No-Zero Integers?
The standard iterative solution runs in O(n log n) time because up to n candidate pairs may be tested and each digit validation takes O(log n). Space complexity is O(1) since only a few integer variables are used. A randomized method can reduce the expected runtime but still performs the same O(log n) digit checks.