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

2021年3月25日12:33:12 发表评论 991 次浏览

本文概述

给定正整数N, 任务是找到位数之和为N的最小数字。

例子:

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

Input: 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#

// 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个项将是=
(N \ bmod 9 +1)* 10 ^ \ frac {N} {9}-1

下面是上述方法的实现

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#

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

输出如下

19

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: