Given an integer N, the task is to find the smallest number whose sum of digits is N2.
Examples:
Input: N = 4
Output: 79
24 = 16
sum of digits of 79 = 76Input: N = 6
Output: 9999
210 = 1024 which has 4 digits
Approach: The idea is to find the general term for the smallest number whose sum of digits is square of N. That is
// First Few terms First Term = 1 // N = 1 Second Term = 4 // N = 2 Third Term = 9 // N = 3 Fourth Term = 79 // N = 4 . . Nth Term:
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
<sup>(n^2 \% 9 + 1) * 10 ^ {\lfloor n^2/9 \rfloor} - 1 </sup>
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to return smallest// number whose sum of digits is n^2int smallestNum(int n){ return (n * n % 9 + 1) * pow(10, n * n / 9) - 1;}// Driver Codeint main(){ int n = 4; cout << smallestNum(n); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{// Function to return smallest// number whose sum of digits is n^2static int smallestNum(int n){ return (int)((n * n % 9 + 1) * Math.pow(10, n * n / 9) - 1);}// Driver Codepublic static void main(String[] args){ int n = 4; System.out.print(smallestNum(n));}}// This code is contributed by Rajput-Ji |
Python 3
# Python implementation of the above approach # Function to return smallest # number whose sum of digits is n^2 def smallestNum(n): return ((n * n % 9 + 1) * pow(10, int(n * n / 9)) - 1) # Driver Code# Given NN = 4print(smallestNum(N))# This code is contributed by Vishal Maurya. |
C#
// C# implementation of the above approachusing System;class GFG{// Function to return smallest// number whose sum of digits is n^2static int smallestNum(int n){ return (int)((n * n % 9 + 1) * Math.Pow(10, n * n / 9) - 1);}// Driver Codepublic static void Main(String[] args){ int n = 4; Console.Write(smallestNum(n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the above approach // Function to return smallest // number whose sum of digits is n^2 function smallestNum( n) { return parseInt (n * n % 9 + 1) * Math.pow(10, parseInt(n*n / 9)) -1; } // Driver Code let n = 4; document.write(smallestNum(n)); // This code contributed by aashish1995 </script> |
Output
10 79
Time complexity: O(log10n2) for given n, as pow function is being used
Auxiliary space: O(1)
Take a part in the ongoing discussion
