Дадени две цели числа s и г Намерете най -малки възможно число, което има точно D цифри и a сума от цифри равен на s .
Върнете номера като a String . Ако няма такъв номер, върнете се '-1' .
Примери:
mb срещу gb
Вход: s = 9 d = 2
Резултат: 18
Обяснение: 18 е възможно най -малкото число с сумата от цифри = 9 и общи цифри = 2.Вход: s = 20 d = 3
Резултат: 299
Обяснение: 299 е възможно най -малкото число с сумата от цифри = 20 и общи цифри = 3.Вход: s = 1 d = 1
Резултат: 1
Обяснение: 1 е възможно най -малкото число с сумата от цифри = 1 и общи цифри = 1.
Съдържание
- [Подход на груба сила] Итерация последователно - O (D*(10^d)) Време и O (1) пространство
- [Очакван подход] Използване на алчна техника - O (D) време и O (1) пространство
[Подход на груба сила] Итерация последователно - O (D*(10^d)) Време и O (1) пространство
C++Тъй като числата са последователни на подход на груба сила итерация от най -малки D-цифрен номер към най -големият Проверка на всеки един. За всеки номер изчисляваме Сума от неговите цифри и върнете първия валиден мач, гарантирайки, че е избран възможно най -малък номер. Ако няма валиден номер, ние се връщаме '-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));
Изход
18
[Очакван подход] Използване на алчна техника - O (D) време и O (1) пространство
Подходът гарантира най -лявата цифра е не нула Така че ние Резерв 1 за него и разпределете останалата сума от отдясно наляво за да се формира възможно най -малкото число. The алчен подход помага при поставянето на най -големите възможни стойности (до 9) в най -десните позиции За да запазите номера малък.
Стъпки за прилагане на горната идея:
- Проверете ограниченията, за да се гарантира a валидна сума s може да се формира с помощта на D цифри в противен случай връщане '-1' .
- Инициализирайте резултат като низ от D '0's и Резерв 1 за най -лявата цифра чрез намаляване s с 1 .
- Траверса от отдясно наляво и поставете най -голямата възможна цифра (<= 9) докато актуализирате s съответно.
- Ако s<= 9 Поставете стойността му на текущата позиция и задайте s = 0 За да спрете допълнителни актуализации.
- Присвойте най -лявата цифра чрез добавяне на останалите s за да се гарантира, че остава ненулева .
- Преобразувайте резултат низ на необходимия формат и връщане това е краен изход.
// 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));
Изход
18