Verilen rakam sayısı ve toplamı ile en küçük sayı
GfG Practice'de deneyin 
Çıkış
Çıkış
İki tam sayı verildiğinde S Ve D Bul en küçük tam olarak mümkün olan sayı d rakamı ve bir rakamların toplamı eşit S .
Numarayı şu şekilde döndür: sicim . Eğer böyle bir numara yoksa geri dön '-1' .
Örnekler:
Giriş: s = 9 d = 2
Çıkış: 18
Açıklama: Rakamların toplamı = 9 ve rakamların toplamı = 2 olan mümkün olan en küçük sayı 18'dir.Giriş: s = 20 d = 3
Çıkış: 299
Açıklama: 299, rakamların toplamı = 20 ve rakamların toplamı = 3 olan mümkün olan en küçük sayıdır.Giriş: s = 1 d = 1
Çıkış: 1
Açıklama: 1, rakamların toplamı = 1 ve rakamların toplamı = 1 olan mümkün olan en küçük sayıdır.
İçerik Tablosu
- [Kaba Kuvvet Yaklaşımı] Sıralı Olarak Yineleme - O(d*(10^d)) zaman ve O(1) Uzay
- [Beklenen Yaklaşım] Açgözlü Tekniği Kullanma - O(d) Zaman ve O(1) Uzay
[Kaba Kuvvet Yaklaşımı] Sıralı Olarak Yineleme - O(d*(10^d)) zaman ve O(1) Uzay
C++Sayılar ardışık olduğundan kaba kuvvet yaklaşımı yinelenir en küçük d haneli sayı en büyük her birini kontrol ediyorum. Her sayı için hesapladığımız rakamlarının toplamı ve mümkün olan en küçük sayının seçildiğinden emin olarak ilk geçerli eşleşmeyi döndürün. Geçerli bir sayı yoksa geri döneriz '-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 ));
Çıkış
18
[Beklenen Yaklaşım] Açgözlü Tekniği Kullanma - O(d) Zaman ve O(1) Uzay
Yaklaşım en soldaki rakamı sağlar sıfır değil yani biz rezerv 1 bunun için ve kalan tutarı dağıtın sağdan sola Mümkün olan en küçük sayıyı oluşturmak için. açgözlü yaklaşım mümkün olan en büyük değerlerin (9'a kadar) yerleştirilmesine yardımcı olur. en sağdaki konumlar sayıyı küçük tutmak için.
Yukarıdaki fikri uygulama adımları:
- sağlamak için kısıtlamaları kontrol edin. geçerli toplam kullanılarak oluşturulabilir d rakamı aksi takdirde geri dön '-1' .
- Başlat sonuç bir dizi olarak d '0'lar Ve rezerv 1 için en soldaki rakam azaltarak 1'e kadar .
- Şuradan geçiş: sağdan sola ve yerleştirin mümkün olan en büyük rakam ( <= 9) güncelleme yaparken S buna göre.
- Eğer S <= 9 değerini geçerli konuma yerleştirin ve ayarlayın s = 0 Daha fazla güncellemeyi durdurmak için.
- Ata en soldaki rakam ekleyerek kalanlar kalmasını sağlamak için sıfır olmayan .
- Dönüştür sonuç dizeyi gerekli formata getirin ve geri dönmek son çıktı olarak.
// 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 ));
Çıkış
18
