Biorąc pod uwagę dwie liczby całkowite S I D znajdź najmniejszy możliwa liczba, która ma dokładnie cyfry d i a suma cyfr równy S .
Zwróć liczbę jako a smyczkowy . Jeśli taki numer nie istnieje, zwróć „-1” .
Przykłady:
Wejście: s = 9 d = 2
Wyjście: 18
Wyjaśnienie: 18 to najmniejsza możliwa liczba, której suma cyfr = 9, a całkowita liczba cyfr = 2.Wejście: s = 20 d = 3
Wyjście: 299
Wyjaśnienie: 299 to najmniejsza możliwa liczba, której suma cyfr = 20 i całkowita liczba cyfr = 3.Wejście: s = 1 d = 1
Wyjście: 1
Wyjaśnienie: 1 to najmniejsza możliwa liczba, której suma cyfr = 1 i całkowita liczba cyfr = 1.
Spis treści
- [Podejście brutalnej siły] Iteruj sekwencyjnie - czas O(d*(10^d)) i przestrzeń O(1)
- [Oczekiwane podejście] Używanie zachłannej techniki - O(d) czasu i O(1) przestrzeni
[Podejście brutalnej siły] Iteruj sekwencyjnie - czas O(d*(10^d)) i przestrzeń O(1)
C++Ponieważ liczby są sekwencyjne, podejście brutalnej siły iteruje od najmniejszy d-cyfrowy numer do największy sprawdzając każdy. Dla każdej liczby obliczamy suma jego cyfr i zwróć pierwsze prawidłowe dopasowanie, upewniając się, że wybrano najmniejszą możliwą liczbę. Jeśli nie ma ważnego numeru, zwracamy „-1” .
// C++ program to find the smallest d-digit // number with the given sum using // a brute force approach #include
// 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 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# 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 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));
Wyjście
18
[Oczekiwane podejście] Używanie zachłannej techniki - O(d) czasu i O(1) przestrzeni
Podejście zapewnia cyfrę skrajną lewą jest niezerowy więc my rezerwa 1 za to i rozdaj pozostałą sumę z od prawej do lewej aby utworzyć najmniejszą możliwą liczbę. The chciwe podejście pomaga w umieszczeniu największych możliwych wartości (do 9) w skrajnie prawe pozycje aby liczba była mała.
Kroki wdrożenia powyższego pomysłu:
- Sprawdź ograniczenia, aby upewnić się, że a ważna suma s można utworzyć za pomocą cyfry d w przeciwnym razie wróć „-1” .
- Zainicjuj wynik jako ciąg d „0” I rezerwa 1 dla cyfra znajdująca się najbardziej na lewo poprzez redukcję o 1 .
- Przejście z od prawej do lewej i umieść największa możliwa cyfra (<= 9) podczas aktualizacji S odpowiednio.
- Jeśli S<= 9 umieść jego wartość w bieżącej pozycji i ustaw s = 0 aby zatrzymać dalsze aktualizacje.
- Przypisz cyfra znajdująca się najbardziej na lewo dodając pozostałe s aby mieć pewność, że pozostanie niezerowy .
- Konwertuj wynik ciąg do wymaganego formatu i powrót to jako wynik końcowy.
// C++ program to find the smallest d-digit // number with the given sum using // Greedy Technique #include
// 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 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# 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 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));
Wyjście
18