logo

指定された桁数と桁の合計で最大の数値を検索します

GfG Practice で試してみる 指定された桁数と桁の合計で最大の数値を検索します' title= #practiceLinkDiv { 表示: なし !重要; }

整数を与える s そして d タスクは、指定された桁の合計で最大の数値を見つけることです s そして桁数 d

例:  



入力: s = 9 d = 2
出力: 90

入力: s = 20 d = 3
出力: 992

推奨される実践方法 可能な最大数 試してみてください!

素朴なアプローチ:



すべてを考慮してください メートル 数字を数字にして保持します 最大 最大数を格納する変数 m桁 そして桁の合計は次のようになります s 。 

時間計算量: O(10メートル)。
補助スペース: ○(1)

指定された桁数と桁の合計で最大の数値を見つけます 貪欲なアプローチ  

問題を解決するためのアイデアは次のとおりです。



アイデアは、左端から右端まですべての桁を 1 つずつ埋めて比較することです。 残額 現在の位置で残りの合計が 9 9 以上の場合は 9、それ以外の場合は残りの合計を入れます。数字は左から右に埋められるため、最も高い数字が左側に配置され、最大の数値が得られます。  そして

図: 

' title=

このアイデアを実装するには、次の手順に従います。

  • s がゼロの場合 
    • m=1 の場合は印刷します 0
    • そうでなければ、そのような数字はあり得ません。
  • s > 9*m の場合、そのような数値はあり得ません。
  • for ループを実行する 0~m-1
    • s>=9 の場合、s から 9 を引いて 9 を出力します。
    • それ以外の場合は を出力し、 を次のように設定します 0

上記のアプローチの実装を以下に示します。

C++
// C++ program to find the largest number that can be // formed from given sum of digits and number of digits. #include    using namespace std; // Prints the smallest possible number with digit sum 's' // and 'm' number of digits. void findLargest(int m int s) {  // If sum of digits is 0 then a number is possible  // only if number of digits is 1.  if (s == 0) {  (m == 1) ? cout << 'Largest number is ' << 0  : cout << 'Not possible';  return;  }  // Sum greater than the maximum possible sum.  if (s > 9 * m) {  cout << 'Not possible';  return;  }  // Create an array to store digits of result  int res[m];  // Fill from most significant digit to least  // significant digit.  for (int i = 0; i < m; i++) {  // Fill 9 first to make the number largest  if (s >= 9) {  res[i] = 9;  s -= 9;  }  // If remaining sum becomes less than 9 then  // fill the remaining sum  else {  res[i] = s;  s = 0;  }  }  cout << 'Largest number is ';  for (int i = 0; i < m; i++)  cout << res[i]; } // Driver code int main() {  int s = 9 m = 2;  findLargest(m s);  return 0; } 
C
// C program to find the largest number that can be // formed from given sum of digits and number of digits. #include  // Prints the smallest possible number with digit sum 's' // and 'm' number of digits. void findLargest(int m int s) {  // If sum of digits is 0 then a number is possible  // only if number of digits is 1.  if (s == 0) {  (m == 1) ? printf('Largest number is 0')  : printf('Not possible');  return;  }  // Sum greater than the maximum possible sum.  if (s > 9 * m) {  printf('Not possible');  return;  }  // Create an array to store digits of result  int res[m];  // Fill from most significant digit to least  // significant digit.  for (int i = 0; i < m; i++) {  // Fill 9 first to make the number largest  if (s >= 9) {  res[i] = 9;  s -= 9;  }  // If remaining sum becomes less than 9 then  // fill the remaining sum  else {  res[i] = s;  s = 0;  }  }  printf('Largest number is ');  for (int i = 0; i < m; i++)  printf('%d' res[i]); } // Driver code int main() {  int s = 9 m = 2;  findLargest(m s);  return 0; } // This code is contributed by Sania Kumari Gupta 
Java
// Java program to find the largest number that can be // formed from given sum of digits and number of digits class GFG  {  // Function to print the largest possible number with digit sum 's'  // and 'm' number of digits  static void findLargest(int m int s)  {  // If sum of digits is 0 then a number is possible  // only if number of digits is 1  if (s == 0)  {  System.out.print(m == 1 ? 'Largest number is 0' : 'Not possible');     return ;  }    // Sum greater than the maximum possible sum  if (s > 9*m)  {  System.out.println('Not possible');  return ;  }    // Create an array to store digits of result  int[] res = new int[m];    // Fill from most significant digit to least  // significant digit  for (int i=0; i<m; i++)  {  // Fill 9 first to make the number largest  if (s >= 9)  {  res[i] = 9;  s -= 9;  }    // If remaining sum becomes less than 9 then  // fill the remaining sum  else  {  res[i] = s;  s = 0;  }  }    System.out.print('Largest number is ');  for (int i=0; i<m; i++)  System.out.print(res[i]);  }    // driver program  public static void main (String[] args)   {  int s = 9 m = 2;  findLargest(m s);  } } // Contributed by Pramod Kumar 
Python3
# Python 3 program to find # the largest number that  # can be formed from given # sum of digits and number # of digits. # Prints the smallest  # possible number with digit  # sum 's' and 'm' number of # digits. def findLargest( m s) : # If sum of digits is 0 # then a number is possible # only if number of digits # is 1. if (s == 0) : if(m == 1) : print('Largest number is '  '0'end = '') else : print('Not possible'end = '') return # Sum greater than the  # maximum possible sum. if (s > 9 * m) : print('Not possible'end = '') return # Create an array to  # store digits of # result res = [0] * m # Fill from most significant # digit to least significant # digit. for i in range(0 m) : # Fill 9 first to make # the number largest if (s >= 9) : res[i] = 9 s = s - 9 # If remaining sum  # becomes less than  # 9 then fill the  # remaining sum else : res[i] = s s = 0 print( 'Largest number is 'end = '') for i in range(0 m) : print(res[i]end = '') # Driver code s = 9 m = 2 findLargest(m s) # This code is contributed by Nikita Tiwari. 
C#
// C# program to find the  // largest number that can  // be formed from given sum  // of digits and number of digits using System; class GFG {    // Function to print the   // largest possible number   // with digit sum 's' and   // 'm' number of digits  static void findLargest(int m int s)  {  // If sum of digits is 0   // then a number is possible   // only if number of digits is 1  if (s == 0)  {  Console.Write(m == 1 ?   'Largest number is 0' :   'Not possible');     return ;  }  // Sum greater than the  // maximum possible sum  if (s > 9 * m)  {  Console.WriteLine('Not possible');  return ;  }  // Create an array to   // store digits of result  int []res = new int[m];  // Fill from most significant   // digit to least significant digit  for (int i = 0; i < m; i++)  {  // Fill 9 first to make  // the number largest  if (s >= 9)  {  res[i] = 9;  s -= 9;  }  // If remaining sum becomes   // less than 9 then  // fill the remaining sum  else  {  res[i] = s;  s = 0;  }  }  Console.Write('Largest number is ');  for (int i = 0; i < m; i++)  Console.Write(res[i]);  }    // Driver Code  static public void Main ()  {  int s = 9 m = 2;  findLargest(m s);  } } // This code is Contributed by ajit 
PHP
 // PHP program to find the largest  // number that can be formed from  // given sum of digits and number  // of digits. // Prints the smallest possible  // number with digit sum 's'  // and 'm' number of digits. function findLargest($m $s) { // If sum of digits is 0 then  // a number is possible only if // number of digits is 1. if ($s == 0) { if(($m == 1) == true) echo 'Largest number is '  0; else echo 'Not possible'; return ; } // Sum greater than the // maximum possible sum. if ($s > 9 * $m) { echo 'Not possible'; return ; } // Create an array to store  // digits of result Fill from  // most significant digit to  // least significant digit. for ($i = 0; $i < $m; $i++) { // Fill 9 first to make // the number largest if ($s >= 9) { $res[$i] = 9; $s -= 9; } // If remaining sum becomes  // less than 9 then fill  // the remaining sum else { $res[$i] = $s; $s = 0; } } echo 'Largest number is '; for ($i = 0; $i < $m; $i++) echo $res[$i]; } // Driver code $s = 9; $m = 2; findLargest($m $s); // This code is contributed by m_kit  ?> 
JavaScript
<script> // Javascript program to find the largest number that can be // formed from given sum of digits and number of digits. // Prints the smallest possible number with digit sum 's' // and 'm' number of digits. function findLargest(m s) {  // If sum of digits is 0 then a number is possible  // only if number of digits is 1.  if (s == 0)  {  (m == 1)? document.write('Largest number is ' + 0)  : document.write('Not possible');  return ;  }  // Sum greater than the maximum possible sum.  if (s > 9*m)  {  document.write('Not possible');  return ;  }  // Create an array to store digits of result  let res = new Array(m);  // Fill from most significant digit to least  // significant digit.  for (let i=0; i<m; i++)  {  // Fill 9 first to make the number largest  if (s >= 9)  {  res[i] = 9;  s -= 9;  }  // If remaining sum becomes less than 9 then  // fill the remaining sum  else  {  res[i] = s;  s = 0;  }  }  document.write('Largest number is ');  for (let i=0; i<m; i++)  document.write(res[i]); } // Driver code  let s = 9 m = 2;  findLargest(m s); // This code is contributed by Mayank Tyagi </script> 

出力
Largest number is 90

時間計算量 この解の値は O(m) です。
補助スペース: O(m) ここで、m は指定された整数です。

アプローチ: 貪欲なアルゴリズム

  • 結果を保存する空の文字列を作成します。
  • d が 1 の場合、結果に s を追加して返します。
  • 左端の桁から右端の桁までループします
    a.残りの桁の合計が 9 以上の場合は、結果に 9 を追加し、残りの桁の合計から 9 を減算します。
    b.残りの桁の合計が 9 未満の場合は、残りの桁の合計を結果に追加し、残りの桁を 0 で埋めます。
  • 結果を返す
C++
#include    #include  using namespace std; int largest_number(int s int d) {  if (s == 0) {  return 0;  }  if (s > 9 * d) {  return -1;  }  string result = '';  for (int i = 0; i < d; i++) {  if (s >= 9) {  result += '9';  s -= 9;  } else {  result += to_string(s);  s = 0;  }  if (s == 0 && i < d-1) {  result += string(d-i-1 '0');  break;  }  }  return stoi(result); } int main() {  // Test case 1  cout << largest_number(9 2) << endl; // Output: 90  // Test case 2  cout << largest_number(20 3) << endl; // Output: 992  return 0; } 
Java
import java.util.*; public class Main {  public static int largest_number(int s int d)  {  // If s is 0 then the largest number is 0.  if (s == 0) {  return 0;  }  // If s is greater than 9 times d then it is  // impossible to form a d-digit number whose sum of  // digits is s.  if (s > 9 * d) {  return -1;  }  // Initialize an empty string to store the result.  String result = '';  // Loop through each digit of the number.  for (int i = 0; i < d; i++) {  // If s is greater than or equal to 9 then add  // 9 to the result and subtract 9 from s.  if (s >= 9) {  result += '9';  s -= 9;  }  // Otherwise add s to the result and set s to  // 0.  else {  result += Integer.toString(s);  s = 0;  }  // If s is 0 and there are still digits left to  // fill then fill the remaining digits with 0s  // and break out of the loop.  if (s == 0 && i < d - 1) {  result += String.join(  ''  Collections.nCopies(d - i - 1 '0'));  break;  }  }  // Convert the result to an integer and return it.  return Integer.parseInt(result);  }  public static void main(String[] args)  {  // Test case 1  System.out.println(  largest_number(9 2)); // Output: 90  // Test case 2  System.out.println(  largest_number(20 3)); // Output: 992  } } 
Python3
def largest_number(s d): if s == 0: return 0 if s > 9 * d: return -1 result = '' for i in range(d): if s >= 9: result += '9' s -= 9 else: result += str(s) s = 0 if s == 0 and i < d-1: result += '0' * (d-i-1) break return int(result) # Test case 1 print(largest_number(9 2)) # Output: 90 # Test case 2 print(largest_number(20 3)) # Output: 992 
C#
using System; class Program {  static int LargestNumber(int s int d) {  if (s == 0) {  return 0;  }  if (s > 9 * d) {  return -1;  }  string result = '';  for (int i = 0; i < d; i++) {  if (s >= 9) {  result += '9';  s -= 9;  } else {  result += s.ToString();  s = 0;  }  if (s == 0 && i < d - 1) {  result += new string('0' d - i - 1);  break;  }  }  return int.Parse(result);  }  static void Main(string[] args) {  // Test case 1  Console.WriteLine(LargestNumber(9 2)); // Output: 90  // Test case 2  Console.WriteLine(LargestNumber(20 3)); // Output: 992  } } 
JavaScript
function largestNumber(s d) { if (s == 0) { return 0; } if (s > 9 * d) { return -1; } let result = ''; for (let i = 0; i < d; i++) { if (s >= 9) { result += '9'; s -= 9; } else { result += s.toString(); s = 0; } if (s == 0 && i < d - 1) { result += '0'.repeat(d - i - 1); break; } } return parseInt(result); } // Test cases console.log(largestNumber(9 2)); // Output: 90 console.log(largestNumber(20 3)); // Output: 992 

出力
90 992

時間計算量: O(d)
補助スペース: O(d)