#PracticelinkDiv {näyttö: Ei mitään! }Annetaan kokonaisluku s ja d -d Tehtävä on löytää suurin luku, jolla on annettu numeron summa s ja numeroiden lukumäärä d -d .
jsp
Esimerkkejä:
Suositeltu käytäntö Suurin mahdollinen määrä Kokeile!Tulo: s = 9 d = 2
Lähtö: 90Tulo: s = 20 d = 3
Lähtö: 992
Naiivi lähestymistapa:
Pitää kaikkia m numerot ja pidä a max muuttuja enimmäismäärän tallentamiseksi M -numerot ja numero summa kuten s .
Ajan monimutkaisuus: O (10m).
Aputila: O (1)
Löydä eniten lukumäärä, jossa on annettu numeroiden lukumäärä ja numeroiden summa Ahne lähestymistapa
Alla on idea ratkaista ongelma:
Ajatuksena on täyttää kaikki numerot vasemmalta oikealle oikealle vertaa jäljellä oleva summa 9: llä, jos jäljellä oleva summa on enemmän tai yhtä suuri kuin 9 9 nykyisessä asennossa, aseta jäljellä oleva summa. Koska numerot täytetään vasemmalta oikealle, korkeimmat numerot asetetaan vasemmalle puolelle, joten suurin osa ja .
Kuva:

Seuraa alla olevia vaiheita ajatuksen toteuttamiseksi:
- Jos s on nolla
- Jos m = 1 tuloste 0 -
- Muuten sellaista lukua ei ole mahdollista.
- Jos S> 9*M, niin tällaista lukua ei ole mahdollista.
- Pitää silmukassa 0-M-1
- Jos S> = 9 Vähennä 9 S: stä ja tulosta 9.
- Muuten tulosta ja aseta s 0 - .
Alla on yllä olevan lähestymistavan toteuttaminen:
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>
Tulos
Largest number is 90
Ajan monimutkaisuus tästä liuoksesta on O (M).
Aputila: O (m) missä m annetaan kokonaisluku.
Lähestymistapa: ahne algoritmi
- Luo tyhjä merkkijono tuloksen tallentamiseksi
- Jos d on 1 liite tulos ja palauta se
- Silmukka vasemmasta numerosta oikealle numerolle
a. Jos jäljellä oleva numeroiden summa on suurempi tai yhtä suuri kuin 9 liite 9 tulokseen ja vähennä 9 jäljellä olevasta numeron summasta
b. Jos jäljellä oleva numeroiden summa on alle 9, liitä tulokseen jäljellä oleva numeroiden summa ja täytä jäljellä olevat numerot 0S: llä - Palauta tulos
#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
Tulos
90 992
Ajan monimutkaisuus: O (d)
Aputila: O (d)