מצא את המספר הגדול ביותר עם מספר ספרות נתון וסכום ספרות

מצא את המספר הגדול ביותר עם מספר ספרות נתון וסכום ספרות
נסה את זה בתרגול GFG מצא את המספר הגדול ביותר עם מספר ספרות נתון וסכום ספרות #practiceLinkDiv {תצוגה: אין! חשוב; }

ניתן מספר שלם ג וכן ד המשימה היא למצוא את המספר הגדול ביותר עם סכום ספרות נתון ג ומספר הספרות ד ו

דוגמאות:  

קֶלֶט: s = 9 d = 2
תְפוּקָה: 90

קֶלֶט: s = 20 d = 3
תְפוּקָה: 992

תרגול מומלץ המספר הגדול ביותר האפשרי נסה את זה!

גישה תמימה:

קחו בחשבון את הכל מ ' מספרי ספרות ושמור על מקס משתנה לאחסון המספר המרבי עם מ 'ספרות וסכום ספרות כמו ג ו 

מורכבות זמן: O (10 מ ' ).
שטח עזר: O (1)

מצא את המספר הגדול ביותר עם המספר הנתון של הספרות וסכום הספרות גישה חמדנית  

להלן הרעיון לפתור את הבעיה:

הרעיון הוא לאחד אחד למלא את כל הספרות משמאל ביותר לימין ביותר להשוות את הסכום שנותר עם 9 אם הסכום שנותר הוא יותר או שווה ל 9 9 במיקום הנוכחי אחר שם את הסכום שנותר. מכיוון שהספרות מתמלאות משמאל לימין, הספרות הגבוהות ביותר יונחו בצד שמאל ומכאן לקבל את המספר הגדול ביותר  וכן ו

אִיוּר: 

עקוב אחר השלבים שלהלן ליישום הרעיון:

  • אם S הוא אפס 
    • אם M = 1 הדפס 0
    • אחרת אין מספר כזה אפשרי.
  • אם s> 9*m, אין מספר כזה אפשרי.
  • להריץ לולאה מ 0 עד m-1
    • אם s> = 9 הפחת 9 מ- S והדפס 9.
    • אחר להדפיס s ו- set s 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 להוסיף את התוצאה ולהחזיר אותה
  • לולאה מהספרה השמאלית ביותר לספרה הימנית ביותר
    א. אם סכום הספרות הנותר גדול או שווה ל 9 הוספה 9 לתוצאה ומעורר 9 מסכום הספרות שנותר
    ב. אם סכום הספרות שנותר הוא פחות מ- 9 הוסף את סכום הספרות שנותר לתוצאה ומלא את הספרות הנותרות עם 0s
  • להחזיר את התוצאה
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 (ד)
שטח עזר: O (ד)