Convert Integer to the Sum of Two No-Zero Integers

Convert Integer to the Sum of Two No-Zero Integers - Problem

Math Easy

A 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 = 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 2

› Output: [1,1]

💡 Note: 1 + 1 = 2. Both 1 and 1 are no-zero integers (contain no digit 0)

Example 2 — Larger Number

$ Input: n = 11

› Output: [2,9]

💡 Note: 2 + 9 = 11. Both 2 and 9 contain no zeros. Note: [1,10] would be invalid since 10 contains 0

Example 3 — Three Digit Number

$ Input: n = 101

› Output: [1,100]

💡 Note: Wait, 100 contains zeros! Better solution: [11,90] - but 90 has 0. Actually [99,2] works: 99 + 2 = 101

Constraints

2 ≤ n ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n = 11

Process

Find a, b where a + b = n and neither contains 0

Output

Return [a, b] = [2, 9]

Key Takeaway

🎯 Key Insight: Start with the simplest split and adjust incrementally to avoid zeros in both numbers

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to systematically find two positive integers that sum to n where neither contains the digit 0. Best approach is the optimized incremental search starting with a=1 and incrementing until both a and b=n-a contain no zeros. Time: O(k × log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Splits	O(n × log n)	O(1)	Try every possible way to split n into two parts and check if both contain no zeros
Optimized - Start Simple and Adjust	O(k × log n)	O(1)	Start with a=1 and increment only when necessary to avoid zeros

Brute Force - Try All Splits — Algorithm Steps

Step 1: Loop through a from 1 to n-1
Step 2: Calculate b = n - a
Step 3: Check if both a and b contain no zeros
Step 4: Return [a, b] when valid pair is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start with a=1

Try a=1, b=n-1 and check for zeros

Increment a

If invalid, try a=2, b=n-2, continue until valid

Found Solution

Return first valid pair [a,b] where both have no zeros

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool hasZero(int num) {
    char str[20];
    sprintf(str, "%d", num);
    return strchr(str, '0') != NULL;
}

void solution(int n, int* result) {
    for (int a = 1; a < n; a++) {
        int b = n - a;
        if (!hasZero(a) && !hasZero(b)) {
            result[0] = a;
            result[1] = b;
            return;
        }
    }
    result[0] = 1;
    result[1] = n - 1; // fallback
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result[2];
    solution(n, result);
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log n)

Loop runs n times, each zero-check takes O(log n) time

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

15.2K Views

Medium Frequency

~15 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Splits — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler