What is the least number that must be added to 299 to make the sum square 30 27 20 None?

View Discussion

Improve Article

Save Article

View Discussion

Improve Article

Save Article

Given a positive integers N, the task is to find the smallest number whose sum of digits is N.
Example: 
 

Input: N = 10
Output: 19
Explanation: 1 + 9 = 10 = N

Input: N = 18
Output: 99
Explanation: 9 + 9 = 18 = N

Naive Approach: 
 

• A Naive approach is to run a loop of i starting from 0 and find Sum of digits of i and check if it’s equal to N or not. 

Below is the implementation of the above approach.
 

C++

#include

#include

using namespace std;

int getSum(int n)

{

    int sum = 0;

    while (n != 0) {

        sum = sum + n % 10;

        n = n / 10;

    }

    return sum;

}

void smallestNumber(int N)

{

    int i = 1;

    while (1) {

        if (getSum(i) == N) {

            cout << i;

            break;

        }

        i++;

    }

}

int main()

{

    int N = 10;

    smallestNumber(N);

    return 0;

}

Java

class GFG{

static int getSum(int n)

{

    int sum = 0;

    while (n != 0)

    {

        sum = sum + n % 10;

        n = n / 10;

    }

    return sum;

}

static void smallestNumber(int N)

{

    int i = 1;

    while (1 != 0)

    {

        if (getSum(i) == N)

        {

            System.out.print(i);

            break;

        }

        i++;

    }

}

public static void main(String[] args)

{

    int N = 10;

    smallestNumber(N);

}

}

Python3

def getSum(n):

    sum1 = 0;

    while (n != 0):

        sum1 = sum1 + n % 10;

        n = n // 10;

    return sum1;

def smallestNumber(N):

    i = 1;

    while (1):

        if (getSum(i) == N):

            print(i);

            break;

        i += 1;

N = 10;

smallestNumber(N);

C#

using System;

class GFG{

static int getSum(int n)

{

    int sum = 0;

    while (n != 0)

    {

        sum = sum + n % 10;

        n = n / 10;

    }

    return sum;

}

static void smallestNumber(int N)

{

    int i = 1;

    while (1 != 0)

    {

        if (getSum(i) == N)

        {

            Console.Write(i);

            break;

        }

        i++;

    }

}

public static void Main(String[] args)

{

    int N = 10;

    smallestNumber(N);

}

}

Javascript

Time Complexity: O(N).
Auxiliary space: O(1)

Efficient Approach: 
 

• An efficient approach to this problem is an observation. Let’s see some examples. 
  • If N = 10, then ans = 19
  • If N = 20, then ans = 299
  • If N = 30, then ans = 3999
• So, it is clear that the answer will have all digits as 9 except the first one so that we get the smallest number.
• So, the Nth term will be =

Below is the implementation of the above approach 
 

C++

#include

#include

using namespace std;

void smallestNumber(int N)

{

    cout << (N % 9 + 1)

                    * pow(10, (N / 9))

                - 1;

}

int main()

{

    int N = 10;

    smallestNumber(N);

    return 0;

}

Java

class GFG{

static void smallestNumber(int N)

{

    System.out.print((N % 9 + 1) *

            Math.pow(10, (N / 9)) - 1);

}

public static void main(String[] args)

{

    int N = 10;

    smallestNumber(N);

}

}

Python3

def smallestNumber(N):

    print((N % 9 + 1) * pow(10, (N // 9)) - 1)

N = 10

smallestNumber(N)

C#

using System;

class GFG{

static void smallestNumber(int N)

{

    Console.WriteLine((N % 9 + 1) *

             Math.Pow(10, (N / 9)) - 1);

}

public static void Main()

{

    int N = 10;

    smallestNumber(N);

}

}

Javascript

Time complexity: O(logN) since inbuilt pow function is being used
Auxiliary space: O(1), since no extra space has been taken.