Nombre més petit amb un recompte i suma de dígits
Proveu -ho a la pràctica GFG 
Producció
Producció
Donat dos nombres enters s i d Troba el més petit Número possible que té exactament D dígits i un suma de dígits igual a s .
Torneu el número com a corda . Si no existeix aquest número, torna '-1' .
Exemples:
Entrada: s = 9 d = 2
Sortida: 18
Explicació: 18 és el nombre més petit possible amb la suma de dígits = 9 i els dígits totals = 2.Entrada: S = 20 d = 3
Sortida: 299
Explicació: 299 és el nombre més petit possible amb la suma de dígits = 20 i dígits totals = 3.Entrada: s = 1 d = 1
Sortida: 1
Explicació: 1 és el nombre més petit possible amb la suma de dígits = 1 i dígits totals = 1.
Taula de contingut
- [Enfocament de força brute] iterate seqüencialment - o (d*(10^d)) temps i O (1) Espai
- [Aproximació esperada] Utilitzant la tècnica Greedy - O (D) Temps i O (1) Espai
[Enfocament de força brute] iterate seqüencialment - o (d*(10^d)) temps i O (1) Espai
C++Ja que els números són seqüencials el enfocament de la força bruta itera de la més petit number de dígits al més gran comprovant cadascun. Per cada número, calculem el suma dels seus dígits i retorneu la primera coincidència vàlida assegurant que el nombre més petit possible estigui seleccionat. Si no existeix cap número vàlid, tornem '-1' .
// C++ program to find the smallest d-digit // number with the given sum using // a brute force approach #include using namespace std ; string smallestNumber ( int s int d ) { // The smallest d-digit number is 10^(d-1) int start = pow ( 10 d - 1 ); // The largest d-digit number is 10^d - 1 int end = pow ( 10 d ) - 1 ; // Iterate through all d-digit numbers for ( int num = start ; num <= end ; num ++ ) { int sum = 0 x = num ; // Calculate sum of digits while ( x > 0 ) { sum += x % 10 ; x /= 10 ; } // If sum matches return the number // as a string if ( sum == s ) { return to_string ( num ); } } // If no valid number is found return '-1' return '-1' ; } // Driver Code int main () { int s = 9 d = 2 ; cout < < smallestNumber ( s d ) < < endl ; return 0 ; }
Java // Java program to find the smallest d-digit // number with the given sum using // a brute force approach import java.util.* ; class GfG { static String smallestNumber ( int s int d ) { // The smallest d-digit number is 10^(d-1) int start = ( int ) Math . pow ( 10 d - 1 ); // The largest d-digit number is 10^d - 1 int end = ( int ) Math . pow ( 10 d ) - 1 ; // Iterate through all d-digit numbers for ( int num = start ; num <= end ; num ++ ) { int sum = 0 x = num ; // Calculate sum of digits while ( x > 0 ) { sum += x % 10 ; x /= 10 ; } // If sum matches return the number // as a string if ( sum == s ) { return Integer . toString ( num ); } } // If no valid number is found return '-1' return '-1' ; } // Driver Code public static void main ( String [] args ) { int s = 9 d = 2 ; System . out . println ( smallestNumber ( s d )); } }
Python # Python program to find the smallest d-digit # number with the given sum using # a brute force approach def smallestNumber ( s d ): # The smallest d-digit number is 10^(d-1) start = 10 ** ( d - 1 ) # The largest d-digit number is 10^d - 1 end = 10 ** d - 1 # Iterate through all d-digit numbers for num in range ( start end + 1 ): sum_digits = 0 x = num # Calculate sum of digits while x > 0 : sum_digits += x % 10 x //= 10 # If sum matches return the number # as a string if sum_digits == s : return str ( num ) # If no valid number is found return '-1' return '-1' # Driver Code if __name__ == '__main__' : s d = 9 2 print ( smallestNumber ( s d ))
C# // C# program to find the smallest d-digit // number with the given sum using // a brute force approach using System ; class GfG { static string smallestNumber ( int s int d ) { // The smallest d-digit number is 10^(d-1) int start = ( int ) Math . Pow ( 10 d - 1 ); // The largest d-digit number is 10^d - 1 int end = ( int ) Math . Pow ( 10 d ) - 1 ; // Iterate through all d-digit numbers for ( int num = start ; num <= end ; num ++ ) { int sum = 0 x = num ; // Calculate sum of digits while ( x > 0 ) { sum += x % 10 ; x /= 10 ; } // If sum matches return the number // as a string if ( sum == s ) { return num . ToString (); } } // If no valid number is found return '-1' return '-1' ; } // Driver Code public static void Main () { int s = 9 d = 2 ; Console . WriteLine ( smallestNumber ( s d )); } }
JavaScript // JavaScript program to find the smallest d-digit // number with the given sum using // a brute force approach function smallestNumber ( s d ) { // The smallest d-digit number is 10^(d-1) let start = Math . pow ( 10 d - 1 ); // The largest d-digit number is 10^d - 1 let end = Math . pow ( 10 d ) - 1 ; // Iterate through all d-digit numbers for ( let num = start ; num <= end ; num ++ ) { let sum = 0 x = num ; // Calculate sum of digits while ( x > 0 ) { sum += x % 10 ; x = Math . floor ( x / 10 ); } // If sum matches return the number // as a string if ( sum === s ) { return num . toString (); } } // If no valid number is found return '-1' return '-1' ; } // Driver Code let s = 9 d = 2 ; console . log ( smallestNumber ( s d ));
Producció
18
[Aproximació esperada] Utilitzant la tècnica Greedy - O (D) Temps i O (1) Espai
L'enfocament garanteix el dígit més esquerre no és zero Així nosaltres Reserva 1 per a això i distribuir la suma restant de de dreta a esquerra per formar el nombre més petit possible. El Aproximació cobdària ajuda a situar els valors més grans possibles (fins a 9) al Posicions més dretes Per mantenir el nombre petit.
Passos per implementar la idea anterior:
- Comproveu les restriccions per assegurar -vos a suma vàlida s es pot formar mitjançant D dígits Altrament, tornar '-1' .
- Inicialitzar resultat Com a cadena de D '0's i Reserva 1 per al Digit més esquerre reduint S per 1 .
- Traverse de de dreta a esquerra i col·locar el més gran dígit possible ( <= 9) mentre s’actualitza s En conseqüència.
- Si s <= 9 Col·loqueu el seu valor a la posició actual i fixeu -lo S = 0 per aturar les actualitzacions posteriors.
- Assignar el Digit més esquerre afegint el queden s Per assegurar -se que quedi no zero .
- Convertir el resultat Cadena al format requerit i retornar És la sortida final.
// C++ program to find the smallest d-digit // number with the given sum using // Greedy Technique #include using namespace std ; string smallestNumber ( int s int d ) { // If sum is too small or too large // for d digits if ( s < 1 || s > 9 * d ) { return '-1' ; } string result ( d '0' ); // Reserve 1 for the leftmost digit s -- ; // Fill digits from right to left for ( int i = d - 1 ; i > 0 ; i -- ) { // Place the largest possible value <= 9 if ( s > 9 ) { result [ i ] = '9' ; s -= 9 ; } else { result [ i ] = '0' + s ; s = 0 ; } } // Place the leftmost digit ensuring // it's non-zero result [ 0 ] = '1' + s ; return result ; } // Driver Code int main () { int s = 9 d = 2 ; cout < < smallestNumber ( s d ) < < endl ; return 0 ; }
Java // Java program to find the smallest d-digit // number with the given sum using // Greedy Technique import java.util.* ; class GfG { static String smallestNumber ( int s int d ) { // If sum is too small or too large // for d digits if ( s < 1 || s > 9 * d ) { return '-1' ; } char [] result = new char [ d ] ; Arrays . fill ( result '0' ); // Reserve 1 for the leftmost digit s -- ; // Fill digits from right to left for ( int i = d - 1 ; i > 0 ; i -- ) { // Place the largest possible value <= 9 if ( s > 9 ) { result [ i ] = '9' ; s -= 9 ; } else { result [ i ] = ( char ) ( '0' + s ); s = 0 ; } } // Place the leftmost digit ensuring // it's non-zero result [ 0 ] = ( char ) ( '1' + s ); return new String ( result ); } // Driver Code public static void main ( String [] args ) { int s = 9 d = 2 ; System . out . println ( smallestNumber ( s d )); } }
Python # Python program to find the smallest d-digit # number with the given sum using # Greedy Technique def smallestNumber ( s d ): # If sum is too small or too large # for d digits if s < 1 or s > 9 * d : return '-1' result = [ '0' ] * d # Reserve 1 for the leftmost digit s -= 1 # Fill digits from right to left for i in range ( d - 1 0 - 1 ): # Place the largest possible value <= 9 if s > 9 : result [ i ] = '9' s -= 9 else : result [ i ] = str ( s ) s = 0 # Place the leftmost digit ensuring # it's non-zero result [ 0 ] = str ( 1 + s ) return '' . join ( result ) # Driver Code if __name__ == '__main__' : s d = 9 2 print ( smallestNumber ( s d ))
C# // C# program to find the smallest d-digit // number with the given sum using // Greedy Technique using System ; class GfG { static string smallestNumber ( int s int d ) { // If sum is too small or too large // for d digits if ( s < 1 || s > 9 * d ) { return '-1' ; } char [] result = new char [ d ]; Array . Fill ( result '0' ); // Reserve 1 for the leftmost digit s -- ; // Fill digits from right to left for ( int i = d - 1 ; i > 0 ; i -- ) { // Place the largest possible value <= 9 if ( s > 9 ) { result [ i ] = '9' ; s -= 9 ; } else { result [ i ] = ( char ) ( '0' + s ); s = 0 ; } } // Place the leftmost digit ensuring // it's non-zero result [ 0 ] = ( char ) ( '1' + s ); return new string ( result ); } // Driver Code static void Main () { int s = 9 d = 2 ; Console . WriteLine ( smallestNumber ( s d )); } }
JavaScript // JavaScript program to find the smallest d-digit // number with the given sum using // Greedy Technique function smallestNumber ( s d ) { // If sum is too small or too large // for d digits if ( s < 1 || s > 9 * d ) { return '-1' ; } let result = Array ( d ). fill ( '0' ); // Reserve 1 for the leftmost digit s -- ; // Fill digits from right to left for ( let i = d - 1 ; i > 0 ; i -- ) { // Place the largest possible value <= 9 if ( s > 9 ) { result [ i ] = '9' ; s -= 9 ; } else { result [ i ] = String ( s ); s = 0 ; } } // Place the leftmost digit ensuring // it's non-zero result [ 0 ] = String ( 1 + s ); return result . join ( '' ); } // Driver Code let s = 9 d = 2 ; console . log ( smallestNumber ( s d ));
Producció
18
