Last Updated: 25 Apr, 2021
Convert Integer to the Sum of Two No-Zero Integers
Moderate
Asked in company
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.
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
Approaches
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).
- Loop until ‘n’ is non-zero.
- Check if (n % 10) is non-zero. Otherwise, return false.
- Divide n by 10.
- 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].
- 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.
The basic idea of this approach is to start building two non-zero numbers from the least significant digit. Let's say we get a digit ‘x’ such that 2 <= ‘x’ <= 9 in the ‘N’. We can simply have 1 and ‘x’ - 1 as a digit in ‘A’ and ‘B’ respectively. The only problem arises when ‘x’ is either 0 or 1. We can handle this case separately. For ‘x’ == 1, we can have 2 and 9 as a digit in ‘A’ and ‘B’ respectively. For ‘x’ == 0, we have 1 and 9 as a digit in ‘A’ and ‘B’ respectively.
Consider the following steps:
- Create two variables ‘A’, ‘B’ and initialise it with 0.
- Also, create a variable “step” and initialise it with 1 which stores the current step.
- Loop until ‘N’ is not zero
- Store the least significant digit of ‘N’ in a variable called ‘d’. Divide ‘N’ by 10.
- Now, if ‘d’ is either 0 or 1 and ‘N’ is greater than 0.
- Update ‘A’ as A = (d + 1) * step
- Update ‘B’ as B = 9 * step
- N = N - 1
- Otherwise, we can update ‘A’ as A += step*1 and ‘B’ as B += step*(d-1)
- Update the “step” as step *= 10