1317. Convert Integer to the Sum of Two No-Zero Integers


Problem Description

The "No-Zero integer" problem requires us to find two positive integers (a and b) such that when they are added together, they equal a given integer n, and neither a nor b contains the digit 0 in their decimal representation. In other words, we need to find a pair of integers where each integer does not have any zeroes, and their sum is exactly n.

Intuition

The intuition behind the solution is to sequentially check pairs of integers that add up to n. We start by setting the first number a to 1 and compute the second number b as n - a. Each time, we convert the numbers to their string representation and check if the character 0 is present in either. If 0 is not found in both a and b, we have found our pair of No-Zero integers and return them as a list [a, b].

The reason we start with a at 1 is because we are looking for positive integers (integers greater than 0), and we increase a by 1 each iteration up to n-1 since the smallest valid b is 1. This approach is guaranteed to find a valid solution because there must be at least one pair without the digit 0 in the range from 1 to n-1 based on the constraints given in the problem. By checking each possible pair, we will surely encounter a valid pair that meets the conditions.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution utilizes a simple brute force approach to implement the algorithm because it systematically checks each pair of positive integers (a, b) such that a + b = n and ensures neither a nor b contains the digit 0.

To iterate through the possible pairs, we use a for loop, starting a at 1 and incrementing a by 1 each time until n-1. This is because a cannot be 0 and b cannot be less than 1.

In Python, within the loop, for each value of a, we calculate b by subtracting a from n (b = n - a). We need to check if either of these numbers includes the digit 0. To do this, we convert both numbers to strings using the str() function, concatenate them, and check for the presence of the character '0'.

We use the not in operator to check if '0' is not present in the concatenated string of a and b. If '0' is not present, this means both a and b are No-Zero integers, and we can then return them as a list [a, b].

Here's the snippet of code encapsulated in the implementation strategy:

1class Solution:
2    def getNoZeroIntegers(self, n: int) -> List[int]:
3        for a in range(1, n):
4            b = n - a
5            if "0" not in str(a) + str(b):
6                return [a, b]

No additional data structures are needed for this implementation. The pattern used here is straightforward enumeration, which refers to trying all possible solutions until the correct one is found. This pattern is often used when the search space is small enough to be practicable, which is the case here since it is guaranteed that there will be at least one valid pair (a, b) within the range from 1 to n-1.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we are given an integer n = 11. Our task is to find two No-Zero integers a and b such that their sum equals n.

We start by initializing a to 1 since it needs to be a positive integer. We then calculate b as n - a, which in this case would be 11 - 1 = 10. Since b contains the digit 0, this pair does not satisfy the condition.

Next, we increment a to 2 and calculate the new b as 11 - 2 = 9. Neither a=2 nor b=9 contain the digit 0, so this pair satisfies the condition and can be returned as a valid answer.

The function would therefore return [2, 9] as output since both are positive integers, their sum is 11, and neither contains the digit 0 in their decimal representation.

Here's how the code would execute the above logic:

1class Solution:
2    def getNoZeroIntegers(self, n: int) -> List[int]:
3        for a in range(1, n):
4            b = n - a
5            if "0" not in str(a) + str(b):
6                return [a, b]
7
8# Example usage:
9solution = Solution()
10result = solution.getNoZeroIntegers(11)
11print(result)  # Output will be [2, 9]

In this example, the brute force solution quickly finds the right pair by simply checking all possibilities in a sequential manner, ensuring the logic is both understandable and efficient for small values of n.

Not Sure What to Study? Take the 2-min Quiz:

Which of the following uses divide and conquer strategy?

Python Solution

1class Solution:
2    # Define a function to find two integers that add up to `n`,
3    # none of which contains the digit 0.
4    def getNoZeroIntegers(self, n: int) -> List[int]:
5        # Iterate through all numbers from 1 to n-1
6        for num1 in range(1, n):
7            # Calculate the second number as the difference between n and the first number
8            num2 = n - num1
9          
10            # Convert both numbers to strings and check if '0' is not present in either
11            if "0" not in str(num1) + str(num2):
12                # If neither contains '0', return the pair of numbers as a list
13                return [num1, num2]
14
15# Note: You must import List from typing before using it
16from typing import List  # This should be at the top of the file
17

Java Solution

1class Solution {
2
3    // This method returns an array of two integers that add up to 'n' and contain no zeroes.
4    public int[] getNoZeroIntegers(int n) {
5        // Start trying with 'a' starting at 1 and incrementing.
6        for (int a = 1;; a++) {
7            // Calculate 'b' so that the sum of 'a' and 'b' equals 'n'.
8            int b = n - a;
9          
10            // Convert both 'a' and 'b' to a string and check if the concatenated result contains '0'.
11            if (!containsZero(a) && !containsZero(b)) {
12                // If neither 'a' nor 'b' contains '0', we return the pair as the result.
13                return new int[] {a, b};
14            }
15        }
16    }
17  
18    // Helper method to check if an integer contains the digit '0'.
19    private boolean containsZero(int number) {
20        // Convert the number to a string.
21        String numberStr = Integer.toString(number);
22        // Return true if the string representation contains '0', otherwise false.
23        return numberStr.contains("0");
24    }
25}
26

C++ Solution

1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7    // Function that returns two positive integers that add up to n, and neither of which contain any zero digits.
8    vector<int> getNoZeroIntegers(int n) {
9        // Start a loop which will iterate until we find a valid pair (a, b)
10        for (int num1 = 1;; ++num1) { // Only increment num1, num2 is derived from n and num1
11            int num2 = n - num1; // Compute the second number of the pair
12          
13            // Convert both numbers to strings and concatenate
14            string combinedStr = to_string(num1) + to_string(num2);
15          
16            // Find if the combined string contains a zero
17            if (combinedStr.find('0') == string::npos) { // npos is returned if character not found
18                // If no zero is found, return the pair as a vector of two integers
19                return {num1, num2};
20            }
21            // If a zero is found, the loop continues, num1 is incremented and we try the next pair
22        }
23    }
24};
25

Typescript Solution

1// Import the necessary functionality for string manipulation in TypeScript
2function getNoZeroIntegers(n: number): number[] {
3    // This function finds two positive integers that add up to 'n', 
4    // and neither of them contain any zero digits.
5
6    // Start a loop which will iterate until we find a valid pair of integers
7    for (let num1 = 1;; ++num1) { // Only increment num1, num2 is derived from n - num1
8        let num2 = n - num1; // Compute the second number of the pair
9      
10        // Convert both numbers to strings to check for the presence of zero
11        let combinedStr = num1.toString() + num2.toString();
12      
13        // Check if the combined string does not contain a '0'
14        if (!combinedStr.includes('0')) {
15            // If no zero is found, return the pair as an array of two numbers
16            return [num1, num2];
17        }
18        // If a zero is found, continue the loop, increment num1, and try again with the next pair.
19    }
20    // The loop is theoretically infinite, but it will always find a solution before reaching n
21    // because there's guaranteed to be at least one such pair according to the problem statement.
22}
23
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(N), where N is the input value to the function. It's because the code uses a loop that runs from 1 up to n - 1 in the worst case, testing each value of a and calculating b as n - a. Since it checks each pair (a, b) once without any nested loops, the time complexity is linear with respect to the input number n.

Space Complexity

The space complexity of the code is O(1). Aside from the input and the two variables a and b that are used within the loop, no additional space that scales with the input size is used. The output list [a, b] is of constant size (2 elements) and does not affect the space complexity.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫