Convert Integer to the Sum of Two No-Zero Integers

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
2 upvotes
Asked in company
Microsoft

Problem statement

Ankur and Deepa are two good friends. Ankur always likes to challenge Deepa with interesting mathematical problems. For a given integer ‘N’ Ankur wants his friend Deepa to find a pair of positive integers [A, B] such that A + B == ‘N’. Since Ankur is an intelligent boy, he adds an additional constraint over ‘A’ and ‘B’. Both integers should not contain any 0 in their decimal representation. Please help Deepa to solve this problem.

Note :

Please assume that there is at least one valid solution.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains an integer ‘N’.

Output Format :

For each test case, the output will be “1” if you have returned the correct answer, else it will be “0”.

The output of each test case will be printed in a separate line.


Note: You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 50
1 <= N <= 10000

Where ‘T’ is the number of test cases, ‘N’ is the given number.

Time limit: 1 sec

Sample Input 1 :

2
7
11

Sample output 1 :

1
1

Explanation of Sample output 1 :

For the first test case, there are multiple valid solutions like [1, 6], [2, 5], [3, 4], [4, 3], [5, 2, [6, 1]. The answer will be a pair having a minimum value of A i.e. [1, 6].

For the second test case, [2, 9] will be the valid answer.

Sample Input 2 :

2
2
1010

Sample output 2 :

1
1
Hint

Can you think of considering every possible pair?

Approaches (2)
Brute force

The basic idea of this approach is to consider every possible pair [A, B] such that A + B == ‘N’ and check if both ‘A’ and ‘B’ do not contain 0 as a digit.

Let us try to implement a function withoutZero(int n) which takes a positive integer ‘n’ and returns true if it doesn’t contain any 0 in its decimal representation otherwise returns false.

The idea here is to go through each digit of its decimal representation and check if it is zero or not.

Now, consider the following steps to implement withoutZero(int n).

  1. Loop until ‘n’ is non-zero.
    • Check if (n % 10) is non-zero. Otherwise, return false.
    • Divide n by 10.
  2. Return true because the given number does not contain any 0 in its decimal representation.

Consider the following steps to find the valid pair [A, B].

  1. Create a loop using a variable ‘a’ such that 1 <= ‘a’ <= ‘N’ - 1
    • Check if ‘a’ and ‘N’ - ‘a’ do not contain any zero in their decimal representation. We can use the function withoutZero() for this task. If both of them don’t contain then store them in an array/list and return it.
Time Complexity

O(N * log(N)), where ‘N’ is the given integer.

 

Since we are looping through 1 to ‘N’ - 1 and at each step we are calling withoutZero() function two times which takes O(log(N)) time as the inner loop of withoutZero(N) function takes O(No of digits in N) time which is basically O(log(N)). So the overall time complexity will be O(N) * O(log(N)) = O(N * log(N)).  

Space Complexity

O(1)

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
Convert Integer to the Sum of Two No-Zero Integers
Full screen
Console