A legkisebb szám az adott számjegyű számmal és összeggel
Próbálja ki a GFG gyakorlaton 
Kibocsátás
Kibocsátás
Két egész számot adott S és D Keresse meg a legkisebb lehetséges szám, amely pontosan rendelkezik D számjegyek és a számjegyek összege egyenlő S -
Visszaadja a számot a húr - Ha nem létezik ilyen szám visszatérés '-1' -
Példák:
Bemenet: s = 9 d = 2
Kimenet: 18
Magyarázat: A 18 a lehető legkisebb szám, a számjegyek összegével = 9 és az összes számjegy = 2.Bemenet: S = 20 d = 3
Kimenet: 299
Magyarázat: A 299 a lehető legkisebb szám, a számjegyek összegével = 20 és az összes számjegy = 3.Bemenet: s = 1 d = 1
Kimenet: 1
Magyarázat: Az 1 a lehető legkisebb szám, a számjegyek összegével = 1 és az összes számjegy = 1.
Tartalomjegyzék
- [Brute -erő megközelítés] iteráció egymás után - o (d*(10^d)) idő és o (1) tér
- [Várt megközelítés] kapzsi technika alkalmazásával - o (d) idő és o (1) tér
[Brute -erő megközelítés] iteráció egymás után - o (d*(10^d)) idő és o (1) tér
C++Mivel a számok szekvenciálisak a brutális erő megközelítés iterálja a legkisebb D számjegyszám a legnagyobb mindegyik ellenőrzése. Minden számra kiszámítjuk a számjegyeinek összege és adja vissza az első érvényes mérkőzést, biztosítva a lehető legkisebb számot. Ha nincs érvényes szám, akkor visszatérünk '-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 ));
Kibocsátás
18
[Várt megközelítés] kapzsi technika alkalmazásával - o (d) idő és o (1) tér
A megközelítés biztosítja a baloldali számjegyet nem nulla Tehát mi 1 -es tartalék érte, és ossza el a fennmaradó összeget Jobbról balra A lehető legkisebb szám kialakításához. A kapzsi megközelítés segít a lehető legnagyobb értékek (legfeljebb 9) elhelyezésében a jobboldali pozíciók hogy a szám kicsi maradjon.
A fenti ötlet megvalósításához szükséges lépések:
- Ellenőrizze a korlátozásokat a érvényes összeg Készíthető a felhasználásával D számjegyek különben visszatér '-1' -
- Inicializál eredmény mint egy karakterlánc D '0 -ek és 1 -es tartalék a baloldali számjegy redukcióval s 1 -
- Átjár Jobbról balra és helyezze a A lehető legnagyobb számjegy ( <= 9) A frissítés közben S ennek megfelelően.
- Ha S <= 9 Helyezze értékét az aktuális helyzetbe, és állítsa be s = 0 A további frissítések leállításához.
- Hozzárendelje a baloldali számjegy hozzáadva a fennmaradó s annak biztosítása érdekében, hogy megmaradjon nulla -
- Konvertálja a eredmény karakterlánc a szükséges formátumhoz és visszatérés Ez a végső kimenet.
// 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 ));
Kibocsátás
18
