codelessgenie blog

Find Two Numbers with Sum N Such That Neither Contains Digit K: A Comprehensive Guide

In programming and number theory, problems involving digit constraints often require a mix of creativity and systematic thinking. One such problem is: Given a positive integer ( N ) and a digit ( K ) (0-9), find two non-negative integers ( a ) and ( b ) such that ( a + b = N ) and neither ( a ) nor ( b ) contains the digit ( K ) in any of their positions.

This problem has practical applications in validation (e.g., ensuring numbers in a system avoid specific digits) and algorithm design (e.g., optimizing for large inputs). In this blog, we’ll break down the problem, explore solution approaches, and highlight best practices to solve it efficiently.

2026-07

Table of Contents#

  1. Introduction
  2. Problem Statement
  3. Approach to Solve the Problem
  4. Step-by-Step Explanation
  5. Example Walkthroughs
  6. Common Edge Cases
  7. Best Practices
  8. Implementation
  9. Conclusion
  10. References

Problem Statement#

Input: Two integers ( N ) (positive, ( N \geq 1 )) and ( K ) (digit, ( 0 \leq K \leq 9 )).
Output: A pair of non-negative integers ( (a, b) ) such that:

  • ( a + b = N )
  • Neither ( a ) nor ( b ) contains the digit ( K ) in any of their decimal places.
    If no such pair exists, return -1.

Approach to Solve the Problem#

We’ll explore two approaches: a brute force method for small ( N ) and a digit-wise construction method for large ( N ).

Brute Force Method#

Idea: Iterate through all possible values of ( a ) from ( 0 ) to ( N ), compute ( b = N - a ), and check if neither ( a ) nor ( b ) contains the digit ( K ).

Time Complexity: ( O(N \cdot D) ), where ( D ) is the number of digits in ( N ) (since checking if a number contains ( K ) takes ( O(D) ) time).
Use Case: Small ( N ) (e.g., ( N \leq 10^6 )), where iteration is feasible.

Digit-Wise Construction for Large N#

For very large ( N ) (e.g., ( N \geq 10^{12} )), brute force is impractical. Instead, we construct ( a ) and ( b ) digit by digit, ensuring their sum equals ( N ) and neither contains ( K ).

Idea: Treat ( N ) as a string, process its digits from least significant to most, and greedily assign digits to ( a ) and ( b ) such that:

  • Their sum (plus carry from the previous digit) equals the current digit of ( N ).
  • Neither digit (in ( a ) or ( b )) is ( K ).

Time Complexity: ( O(D) ), where ( D ) is the number of digits in ( N ).
Use Case: Large ( N ) where brute force is infeasible.

Step-by-Step Explanation#

Brute Force Method#

  1. Iterate ( a ) from 0 to ( N ): For each ( a ), compute ( b = N - a ).
  2. Check digits of ( a ) and ( b ): For each pair ( (a, b) ), verify that neither contains ( K ).
  3. Return the first valid pair: Since we iterate from ( a = 0 ) upwards, the first valid pair found is the lexicographically smallest (though any valid pair is acceptable).

Digit-Wise Construction#

  1. Convert ( N ) to a reversed string: Process digits from least significant to most (e.g., ( N = 567 ) becomes ["7", "6", "5"]).
  2. Initialize carry and digit lists: Track carry between digits and build lists for ( a ) and ( b ) digits.
  3. Process each digit: For each digit ( d ) in reversed ( N ):
    • Determine valid carry_out candidates: try 0 first, then 1 if needed.
    • For each candidate carry_out, compute sum_needed = ( d + 10 \times \text{carry_out} - \text{carry_in} ).
    • Iterate possible digits ( a_digit ) (0-9, excluding ( K )).
    • Compute ( b_digit = \text{sum_needed} - a_digit ). Check if ( b_digit ) is between 0-9 and not ( K ).
    • Compute carry_out using: ( \text{carry_out} = (a_digit + b_digit + \text{carry_in} - d) // 10 ).
    • Proceed to the next digit.
  4. Handle final carry: If after processing all digits, carry is non-zero, the pair is invalid.

Example Walkthroughs#

Example 1: Small N with Brute Force#

Input: ( N = 100 ), ( K = 0 )
Goal: Find ( a ) and ( b ) such that ( a + b = 100 ), and neither contains ( 0 ).

Brute Force Steps:

  • Iterate ( a = 0 ): ( b = 100 ) (contains 0) → invalid.
  • ( a = 1 ): ( b = 99 ). Check digits: ( a=1 ) (no 0), ( b=99 ) (no 0) → valid.

Output: ( (1, 99) ).

Example 2: Large N with Digit-Wise Construction#

Input: ( N = 9876543210 ) (10 digits), ( K = 5 )
Goal: Construct ( a ) and ( b ) without digit 5, summing to ( N ).

Digit-Wise Steps:

  • Reverse ( N ): [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (digits from least to most significant).
  • Process each digit with carry_in and carry_out logic:
    • Least significant digit: total = digit + 10carry_out - carry_in, find a_digit and b_digit such that a_digit + b_digit + carry_in = digit + 10carry_out.
    • Continue processing, updating carry_out correctly at each position.

Result: This greedy digit-wise algorithm attempts to construct a pair by processing each digit sequentially. Note that it is a heuristic method and does not guarantee finding a solution even when one exists, as it does not backtrack when earlier choices lead to dead ends.

Common Edge Cases#

  • ( N < K ): E.g., ( N=3 ), ( K=5 ). ( a=1 ), ( b=2 ) (both valid).
  • ( K=0 ): Numbers like 10 are invalid (contains 0). Use ( a=1 ), ( b=9 ) for ( N=10 ).
  • No solution: ( N=1 ), ( K=1 ). Possible pairs: (0,1) (1 has K), (1,0) (1 has K) → return -1.
  • Large ( N ) with all digits ( K ): ( N=555 ), ( K=5 ). No valid pairs (all digits are 5, so ( a + b = 555 ) requires digits summing to 5, 5, 5—all K).

Best Practices#

  1. Early Termination in Brute Force: Stop iterating as soon as a valid pair is found to save time.
  2. Efficient Digit Check: For checking if a number contains ( K ), use modulo/division (faster for large numbers) instead of string conversion.
  3. Handle Carry Correctly: In digit-wise construction, use carry_in and carry_out properly: a_digit + b_digit + carry_in = digit + 10 × carry_out.
  4. Validate Inputs: Ensure ( K ) is a digit (0-9) and ( N ) is positive.

Implementation#

Brute Force Code (Python)#

def has_digit(x: int, k: int) -> bool:
    """Check if x contains digit k."""
    if x == 0 and k == 0:
        return True
    while x > 0:
        if x % 10 == k:
            return True
        x = x // 10
    return False
 
def find_pair_brute(n: int, k: int) -> tuple:
    """Brute force approach to find a and b."""
    for a in range(n + 1):
        b = n - a
        if not has_digit(a, k) and not has_digit(b, k):
            return (a, b)
    return (-1,)
 
# Example usage
print(find_pair_brute(100, 0))  # Output: (1, 99)
print(find_pair_brute(1, 1))    # Output: (-1,)

Digit-Wise Construction Code (Python Outline)#

def find_pair_large_n(n: int, k: int) -> tuple:
    n_str = str(n)[::-1]
    a_digits = []
    b_digits = []
    carry_in = 0
 
    for i in range(len(n_str)):
        d = int(n_str[i])
        carry_out = 0
        found = False
 
        while carry_out <= 1:
            sum_needed = d + 10 * carry_out - carry_in
            if sum_needed >= 0 and sum_needed <= 18:
                for a_digit in range(10):
                    if a_digit == k:
                        continue
                    b_digit = sum_needed - a_digit
                    if 0 <= b_digit <= 9 and b_digit != k:
                        computed_carry = (a_digit + b_digit + carry_in - d) // 10
                        if computed_carry == carry_out:
                            a_digits.append(a_digit)
                            b_digits.append(b_digit)
                            carry_in = carry_out
                            found = True
                            break
                if found:
                    break
            carry_out += 1
 
        if not found:
            return (-1,)
 
    if carry_in != 0:
        return (-1,)
 
    a = int(''.join(map(str, a_digits[::-1]))) if a_digits else 0
    b = int(''.join(map(str, b_digits[::-1]))) if b_digits else 0
    return (a, b)
 
# Example usage
print(find_pair_large_n(9876543210, 5))  # Output depends on valid construction

Conclusion#

The problem of finding two numbers summing to ( N ) without digit ( K ) can be solved with brute force for small ( N ) and digit-wise construction for large ( N ). By understanding digit constraints and optimizing for efficiency, we can handle both small and large inputs effectively.

References#