logo

Verilen sayıda rakam ve rakam toplamı ile en büyük sayıyı bulun

GFG uygulamasında deneyin Verilen sayıda rakam ve rakam toplamı ile en büyük sayıyı bulun' title= #PracticelinkDiv {ekran: yok! Önemli; }

Bir tamsayı verildiğinde S Ve D Görev, verilen rakam toplamı ile en büyük sayıyı bulmaktır S ve basamak sayısı D .

Örnekler:  

Giriş: s = 9 d = 2
Çıktı: 90



Giriş: s = 20 d = 3
Çıktı: 992

Önerilen Uygulama Mümkün olan en büyük sayı Deneyin!

Saf yaklaşım:

Hepsini düşün M rakam numaraları ve bir maksimum Maksimum numarayı ile depolamak için değişken m rakamları ve rakam toplamı S

Zaman karmaşıklığı: O (10M).
Yardımcı Alan: O (1)

Verilen rakam sayısı ve rakam toplamı ile en büyük sayıyı bulun Açgözlü yaklaşım  

Aşağıda sorunu çözme fikri:

Fikir, en soldan en sağa en sağa tüm rakamları tek tek doldurur. kalan toplam 9 ile kalan toplam, mevcut pozisyonda 9 9'a eşit veya eşitse, kalan toplamı koyun. Rakamlar soldan sağa doldurulduğundan, en yüksek rakamlar sol tarafa yerleştirilecek, bu nedenle en büyük sayıyı elde edecektir  Ve .

İllüstrasyon: 

' title=

Fikri uygulamak için aşağıdaki adımları izleyin:

  • S sıfırsa 
    • M = 1 yazdırsa 0
    • Aksi takdirde böyle bir sayı mümkün değildir.
  • S> 9*m ise böyle bir sayı mümkün değildir.
  • Bir döngü için çalıştırın 0 ila M-1
    • S> = 9 9'u S'den çıkarın ve 9 yazdırın.
    • Başka bir yazdırın ve S'yi ayarlayın 0 .

Aşağıda yukarıdaki yaklaşımın uygulanmasıdır:

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> 

Çıktı
Largest number is 90

Zaman karmaşıklığı Bu çözümün O (M).
Yardımcı Alan: O (m) burada m verilen tamsayıdır.

Yaklaşım: Açgözlü algoritma

  • Sonucu depolamak için boş bir dize oluşturun
  • D 1 ise, sonuca ekleyin ve iade edin
  • En soldan en sağa doğru en sağa döngü
    A. Geri kalan basamak toplamı 9'dan 9'a eşit veya eşitse, sonucuna 9'u ekleyin ve kalan rakam toplamından 9'u çıkarın.
    B. Geri kalan basamak toplamı 9'dan azsa, kalan rakam toplamını sonucuna ekleyin ve kalan rakamları 0'larla doldurun
  • Sonucu döndür
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 

Çıktı
90 992

Zaman karmaşıklığı: O (d)
Yardımcı Alan: O (d)