주어진 숫자 수와 숫자의 합으로 가장 큰 숫자를 찾으십시오.
GFG 연습에서 시도하십시오 
#PracticElinkDiv {display : none! 중요; }
산출
산출
#PracticElinkDiv {display : none! 중요; } 정수가 주어졌습니다 에스 그리고 디 작업은 주어진 숫자 합계로 가장 큰 숫자를 찾는 것입니다. 에스 그리고 숫자의 수 디 .
예 :
권장 연습 가능한 가장 많은 수 시도해보십시오!입력: s = 9 d = 2
산출: 90입력: s = 20 d = 3
산출: 992
순진한 접근 :
모두 고려하십시오 중 숫자 번호를 유지하고 a 맥스 최대 숫자를 보관할 수있는 변수 M 자리 그리고 숫자 합계 에스 .
시간 복잡성 : O (10 중 ).
보조 공간 : o (1)
주어진 숫자 수와 숫자 합으로 가장 큰 숫자를 찾으십시오. 욕심 많은 접근
아래는 문제를 해결하는 아이디어입니다.
아이디어는 왼쪽에서 가장 오른쪽으로 모든 숫자를 하나씩 채우는 것입니다. 나머지 합계 나머지 합계가 현재 위치에서 9 9에 달하는 경우 9로 9로 나머지 합계를 넣습니다. 숫자는 왼쪽에서 오른쪽으로 채워 지므로 가장 높은 자리는 왼쪽에 배치되므로 가장 큰 숫자를 얻습니다. 그리고 .
삽화:
아래 단계를 따라 아이디어를 구현하십시오.
- S가 0 인 경우
- M = 1 인쇄 인 경우 0
- 그렇지 않으면 그러한 숫자는 불가능합니다.
- s> 9*m이라면 그러한 숫자는 불가능합니다.
- 루프를 위해 실행하십시오 0 ~ M-1
- s> = 9 인 경우 9에서 9를 빼고 인쇄 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에 appled onder incate에 첨부되고 나머지 숫자의 숫자에서 9를 빼냅니다.
비. 나머지 숫자 합이 9 미만인 경우 나머지 숫자는 결과에 나머지 숫자를 추가하고 나머지 숫자를 0으로 채 웁니다. - 결과를 반환하십시오
#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)
