Last Updated: 9 Dec, 2020
Number And Digits
Easy
Asked in companies
You are given a positive number ‘N.’ You need to find all the numbers such that the sum of digits of those numbers to the number itself is equal to ‘N.’
For example:
You are given ‘N’ as 21, the only number whose sum of digits and the number itself equals 21 is 15 as 15 + 1 + 5 = 21. Hence the answer is [15].
Input format :
The first line contains a single integer ‘T’ representing the number of test cases.
Each test case consists of a single integer ‘N’, which represents the given integer.
Output Format :
For each test case, print all the space-separated integers whose sum of digits with themselves is equal to ‘N’ in increasing order, Print -1 if no such integer exists.
Print a separate line for each test case.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^12
Time Limit: 1 sec
Approaches
In this approach, we iterate through the numbers from 1 to N. We will find the sum of its digits and add it to the integer itself for each number. Then, we check if the obtained sum is equal to N.
We create a recursive function called sumOfDigits(num) that returns the sum of digits of the number num.
Algorithm:
- The function sumOfDigits(num)
- If num is equal to 0 return 0
- Otherwise, return num % 10 + sumOfDigits(num / 10) from the function.
- Create an empty array numList.
- Iterate num from 1 to N
- If num + sumOfDigits(num) is equal to N, insert num into numList
- Finally, return the array numList.
The intuition behind this approach is that any integer’s sum of digits can’t be very high, so we check only 1000 numbers less than and greater than the given number.
So we will traverse from 1 to 1000, and find the number whose sum of digits is with the number itself is equal to the given number.
We create a recursive function called sumOfDigits(num) that returns the sum of digits of the number num.
Algorithm:
- The function sumOfDigits(num)
- If num is equal to 0 return 0
- Otherwise, return num % 10 + sumOfDigits(num / 10) from the function.
- Create an empty array numList.
- Iterate num from 1 to 1000.
- Set leftVal as n - num and rightVal as n + num
- If leftVal is greater than 0 and leftVal + sumOfDigits(leftVal) is equal to n, then insert leftVal in numList.
- If rightVal + sumOfDigits(rightVal) is equal to n and rightVal is not equal to leftVal, then insert rightVal in numList.
- Finally, return numList.