算法（查找数字总和为N的最小数字）

本文概述

C ++
Java
Python3
C#
C ++
Java
Python3
C#

给定正整数N, 任务是找到位数之和为N的最小数字。
【算法（查找数字总和为N的最小数字）】例子：

Input: N = 10 Output: 19 Explanation: 1 + 9 = 10 = NInput: N = 18 Output: 99 Explanation: 9 + 9 = 18 = N

天真的方法：

天真的方法是从0开始运行i的循环并查找数字总和的i并检查它是否等于N。

下面是上述方法的实现。
C ++

// C++ program to find the smallest // number whose sum of digits is also N #include < iostream> #include < math.h> using namespace std; // Function to get sum of digits int getSum( int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // Function to find the smallest // number whose sum of digits is also N void smallestNumber( int N) { int i = 1; while (1) { // Checking if number has // sum of digits = N if (getSum(i) == N) { cout < < i; break ; } i++; } } // Driver code int main() { int N = 10; smallestNumber(N); return 0; }

Java

// Java program to find the smallest // number whose sum of digits is also N class GFG{ // Function to get sum of digits static int getSum( int n) { int sum = 0 ; while (n != 0 ) { sum = sum + n % 10 ; n = n / 10 ; } return sum; } // Function to find the smallest // number whose sum of digits is also N static void smallestNumber( int N) { int i = 1 ; while ( 1 != 0 ) { // Checking if number has // sum of digits = N if (getSum(i) == N) { System.out.print(i); break ; } i++; } } // Driver code public static void main(String[] args) { int N = 10 ; smallestNumber(N); } } // This code is contributed // by shivanisinghss2110

Python3

# Python3 program to find the smallest # number whose sum of digits is also N # Function to get sum of digits def getSum(n): sum1 = 0 ; while (n ! = 0 ): sum1 = sum1 + n % 10 ; n = n / / 10 ; return sum1; # Function to find the smallest # number whose sum of digits is also N def smallestNumber(N): i = 1 ; while ( 1 ): # Checking if number has # sum of digits = N if (getSum(i) = = N): print (i); break ; i + = 1 ; # Driver code N = 10 ; smallestNumber(N); # This code is contributed by Code_Mech

// C# program to find the smallest // number whose sum of digits is also N using System; class GFG{ // Function to get sum of digits static int getSum( int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // Function to find the smallest // number whose sum of digits is also N static void smallestNumber( int N) { int i = 1; while (1 != 0) {// Checking if number has // sum of digits = N if (getSum(i) == N) { Console.Write(i); break ; } i++; } } // Driver code public static void Main(String[] args) { int N = 10; smallestNumber(N); } } // This code is contributed by Amit Katiyar

输出如下

19

时间复杂度：
上)。
高效方法：

解决此问题的有效方法是观察。我们来看一些例子。
- 如果N = 10, 则ans = 19
- 如果N = 20, 则ans = 299
- 如果N = 30, 则ans = 3999
因此, 很明显答案将除第一个数字外的所有数字均为9, 因此我们得到的数字最小。
因此, 第N个项将是=

文章图片
下面是上述方法的实现
C ++

// C++ program to find the smallest // number whose sum of digits is also N #include < iostream> #include < math.h> using namespace std; // Function to find the smallest // number whose sum of digits is also N void smallestNumber( int N) { cout < < (N % 9 + 1) * pow (10, (N / 9)) - 1; } // Driver code int main() { int N = 10; smallestNumber(N); return 0; }

Java

// Java program to find the smallest // number whose sum of digits is also N class GFG{// Function to find the smallest // number whose sum of digits is also N static void smallestNumber( int N) { System.out.print((N % 9 + 1 ) * Math.pow( 10 , (N / 9 )) - 1 ); }// Driver code public static void main(String[] args) { int N = 10 ; smallestNumber(N); } } // This code is contributed by sapnasingh4991

Python3

# Python3 program to find the smallest # number whose sum of digits is also N # Function to find the smallest # number whose sum of digits is also N def smallestNumber(N): print ((N % 9 + 1 ) * pow ( 10 , (N / / 9 )) - 1 ) # Driver code N = 10 smallestNumber(N) # This code is contributed by Code_Mech

// C# program to find the smallest // number whose sum of digits is also N using System; class GFG{ // Function to find the smallest // number whose sum of digits is also N static void smallestNumber( int N) { Console.WriteLine((N % 9 + 1) * Math.Pow(10, (N / 9)) - 1); } // Driver code public static void Main() { int N = 10; smallestNumber(N); } } // This code is contributed by Ritik Bansal

输出如下