العثور على أكبر عدد مع عدد معين من الأرقام ومجموع الأرقام

العثور على أكبر عدد مع عدد معين من الأرقام ومجموع الأرقام
جربه على ممارسة GfG العثور على أكبر عدد مع عدد معين من الأرقام ومجموع الأرقام #practiceLinkDiv { العرض: لا شيء! مهم؛ }

نظرا لعدد صحيح ق و د المهمة هي العثور على أكبر رقم مع مجموع أرقام معين ق وعدد الأرقام د .

أمثلة:  

مدخل: ق = 9 د = 2
الإخراج: 90

مدخل: ق = 20 د = 3
الإخراج: 992

الممارسة الموصى بها أكبر عدد ممكن جربه!

النهج الساذج:

النظر في كل شيء م أرقام الأرقام والاحتفاظ بها الأعلى متغير لتخزين الحد الأقصى لعدد م أرقام ورقم المبلغ كما ق

تعقيد الوقت: يا (10 م ).
المساحة المساعدة: يا(1)

ابحث عن أكبر رقم يحتوي على عدد الأرقام ومجموع الأرقام النهج الجشع  

فيما يلي فكرة حل المشكلة:

تتمثل الفكرة في ملء جميع الأرقام واحدًا تلو الآخر من أقصى اليسار إلى أقصى اليمين ومقارنة الأرقام المبلغ المتبقي مع 9 إذا كان المبلغ المتبقي أكثر من أو يساوي 9 9 في الموضع الحالي وإلا ضع المبلغ المتبقي. بما أن الأرقام يتم ملؤها من اليسار إلى اليمين، فسيتم وضع أعلى الأرقام على الجانب الأيسر وبالتالي الحصول على أكبر رقم  و .

توضيح: 

اتبع الخطوات التالية لتنفيذ الفكرة:

  • إذا كانت s صفراً 
    • إذا م = 1 الطباعة 0
    • وإلا فلا يوجد مثل هذا العدد ممكن.
  • إذا كانت s > 9*m فهذا يعني أن هذا الرقم غير ممكن.
  • قم بتشغيل حلقة for من 0 إلى م-1
    • إذا كان s>=9، اطرح 9 من s واطبع 9.
    • وإلا قم بطباعة s واضبط 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، قم بإلحاق s بالنتيجة وإعادتها
  • حلقة من الرقم الموجود في أقصى اليسار إلى الرقم الموجود في أقصى اليمين
    أ. إذا كان مجموع الأرقام المتبقية أكبر من أو يساوي 9، ألحق 9 بالنتيجة واطرح 9 من مجموع الأرقام المتبقية
    ب. إذا كان مجموع الأرقام المتبقية أقل من 9، قم بإلحاق مجموع الأرقام المتبقية بالنتيجة واملأ الأرقام المتبقية بالصفر
  • إرجاع النتيجة
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 

تعقيد الوقت: يا (د)
المساحة المساعدة: يا (د)