logo

Намерете най -големия брой с даден брой цифри и сума от цифри

Опитайте го на GFG практика Намерете най -големия брой с даден брой цифри и сума от цифри' title= #practicelinkdiv {display: няма! важно; }

Дадено цяло число s и г Задачата е да се намери най -голямото число с дадена цифрова сума s и броя на цифрите г .

Примери:  



Вход: s = 9 d = 2
Резултат: 90

Вход: s = 20 d = 3
Резултат: 992

Препоръчителна практика Възможен най -голям брой Опитайте!

Наивен подход:



Помислете за всички m цифрови числа и запазете a Макс променлива за съхраняване на максималния номер с m цифри и цифрена сума като s

Сложност на времето: O (10m).
Спомагателно пространство: O (1)

Намерете най -голямото число с дадения брой цифри и сума от цифри Алчен подход  

По -долу е идеята за решаване на проблема:



Идеята е една по една да попълни всички цифри от най -ляво надясно сравнете останала сума с 9, ако останалата сума е повече или равна на 9 9 на текущата позиция, друга позиция, поставете останалата сума. Тъй като цифрите се пълнят отляво надясно, най -високите цифри ще бъдат поставени от лявата страна, следователно получават най -голям брой  и .

Илюстрация: 

' title=

Следвайте стъпките по -долу, за да приложите идеята:

  • Ако S е нула 
    • Ако m = 1 печат 0
    • Иначе не е възможно такъв номер.
  • Ако s> 9*m, тогава не е възможно такова число.
  • Изпълнете A For Loop от 0 до m-1
    • Ако s> = 9 извадете 9 от S и отпечатайте 9.
    • Иначе отпечатайте s и задайте s to to to 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 от останалата сума от цифри
    б. Ако останалата сума от цифри е по -малка от 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 (d)
Спомагателно пространство: O (d)