Problem

Submissions

Hints & solutions

Discuss

Number And Digits

Easy

0/40

Average time to solve is 15m

Contributed by

60 upvotes

Asked in companies

Problem statement

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].

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
21
8

Sample Output1 :

15
4

Explanation :

For the first test case, 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].

For the second test case, you are given ‘N’ as 8, the only number whose sum of digits and the number itself equals 8 is 4 as 4 + 4 = 8. Hence the answer is [4].

Sample Input 2:

2
10
31

Sample Output 2:

5
-1

Hint 1

Hint 2

Think of a brute force approach to solve this problem.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

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

The time complexity to calculate the sum of digits is O(log(N)). We are calculating the sum of digits of N integers. Hence, the overall time complexity is O(N*log(N))

Space Complexity

O(1).

We store an array of integers, but the array will contain very few integers in most cases. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Number And Digits

Console