Number And Digits
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

Question

Number And Digits

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

Accepted Answer

To solve this problem our program should give the output after addition of all the digits of a given number.

For ie. if someone has given input of 163 then our program should give 10 as a output.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(nlogn)Explanation:

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))

Java (SE 1.8)


/*
	Time Complexity: O(N*log(N))
	Space Complexity: O(1)
	
	Where N is the given integer.
*/
import java.util.ArrayList;

public class Solution {
	public static int sumOfDigits(int num) {

		// Base Case
		if (num == 0) {
			return 0;
		}

		// Adding the last digits and recursively calling
		return num % 10 + sumOfDigits(num / 10);
	}

	public static ArrayList numbersAndDigits(int n) {

		// Create an empty array
		ArrayList numList = new ArrayList<>();

		for (int num = 0; num < n + 1; ++num) {

			// Checking if the sum of number and it's digits is equal to N
			if (num + sumOfDigits(num) == n) {
				numList.add(num);
			}
		}

		// Return the array of numbers
		return numList;
	}
}

Python (3.5)

'''

    Time Complexity: O(N*log(N))

    Space Complexity: O(1)



    Where N is the given integer.

'''    



def sumOfDigits(num):



    # Base Case

    if (num == 0):

        return 0



    # Adding the last digits and recursively calling

    return num % 10 + sumOfDigits(num // 10)





def numbersAndDigits(n):



    # Create an empty array

    numList = []



    for num in range(n + 1):



        # Checking if the sum of number and it's digits is equal to N

        if (num + sumOfDigits(num) == n):

            numList.append(num)



    # Return the array of numbers

    return numList

C++ (g++ 5.4)

/*

    Time Complexity: O(N*log(N))

    Space Complexity: O(1)



    Where N is the given integer.

*/



int sumOfDigits(int num)

{

    // Base Case

    if (num == 0)

    {

        return 0;

    }



    // Adding the last digits and recursively calling

    return num % 10 + sumOfDigits(num / 10);

}



vector numbersAndDigits(int n)

{

    // Create an empty array

    vector numList;



    for(int num = 0; num < n + 1; ++num)

    {

        // Checking if the sum of number and it's digits is equal to N

        if (num + sumOfDigits(num) == n)

        {

            numList.push_back(num);

        }

    }



    // Return the array of numbers

    return numList;

}

Accepted Answer

Optimised Approach

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.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(1)Explanation:

O(1).

We are iteration from 1 to 1000 to check the numbers in the range from N -1000 to N + 1000. Hence, the overall time complexity is O(1).

Java (SE 1.8)


/*
	Time Complexity: O(1)
	Space Complexity: O(1)
	
*/

import java.util.ArrayList;
import java.util.Collections;

public class Solution {

	public static int sumOfDigits(int num) {

		// Base Case
		if (num == 0) {
			return 0;
		}

		// Adding the last digits and recursively calling
		return num % 10 + sumOfDigits(num / 10);
	}

	public static ArrayList numbersAndDigits(int n) {

		// Create an empty array
		ArrayList numList = new ArrayList();

		for (int num = 1; num < 1001; ++num) {
			
			// Set the left and right values
			int leftVal = n - num;
			int rightVal = n + num;

			// Check if leftVal and sum of digits of leftVal is equal to N
			if (leftVal >= 0 && leftVal + sumOfDigits(leftVal) == n) {
				numList.add(leftVal);
			}

			// Check if rightVal and sum of digits of rightVal is equal to N
			if (rightVal + sumOfDigits(rightVal) == n && rightVal != leftVal) {
				numList.add(rightVal);
			}
		}

		// Return the array of numbers
		Collections.sort(numList);
		return numList;

	}

}

Python (3.5)

'''

    Time Complexity: O(1)

    Space Complexity: O(1)



'''



def sumOfDigits(num):



    # Base Case

    if (num == 0):

        return 0



    # Adding the last digits and recursively calling

    return num % 10 + sumOfDigits(num // 10)





def numbersAndDigits(n):



    # Create an empty list

    numList = []



    for num in range(1, 1001):



        # Set the left and right values

        leftVal = n - num

        rightVal = n + num



        # Check if sum of leftVal and digits of leftVal is equal to N

        if(leftVal >= 0) and (leftVal + sumOfDigits(leftVal) == n):

            numList.append(leftVal)



        # Check if sum of rightVal and digits of rightVal is equal to N

        if(rightVal + sumOfDigits(rightVal) == n) and (rightVal != leftVal):

            numList.append(rightVal)



    # Return the array of numbers

    numList.sort()

    return numList

C++ (g++ 5.4)

/*

    Time Complexity: O(1)

    Space Complexity: O(1)



*/



#include 



int sumOfDigits(int num)

{

    // Base Case

    if (num == 0)

    {

        return 0;

    }



    // Adding the last digits and recursively calling

    return num % 10 + sumOfDigits(num / 10);

}





vector numbersAndDigits(int n)

{

    // Create an empty array

    vector numList;



    for(int num = 1; num < 1001; ++num) 

    {

        // Set the left and right values

        int leftVal = n - num;

        int rightVal = n + num;



        // Check if sum of leftVal and digits of leftVal is equal to N

        if(leftVal >= 0 && leftVal + sumOfDigits(leftVal) == n)

        {

            numList.push_back(leftVal);

        }



        // Check if sum of rightVal and digits of rightVal is equal to N

        if(rightVal + sumOfDigits(rightVal) == n && rightVal != leftVal)

        {

            numList.push_back(rightVal);

        }

    }



    // Return the array of numbers

    sort(numList.begin(), numList.end());

    return numList;

}

Top Virtusa Consulting Services Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in Virtusa Consulting Services Associate Software Engineer