NAJMENŠIE ČÍSLO S DANÝM ČÍSLICOVÝM POČTOM A SUMOU

Vyskúšajte to v praxi GFG ' title=

Vzhľadom na dve celé čísla siež a d nájsť najmenší možné číslo, ktoré má presne D číslice a a súčet číslic rovný siež .
Vráťte číslo ako a struna . Ak takéto číslo neexistuje návratnosť '-1' .

Príklady:

Vstup: S = 9 d = 2
Výstup: 18
Vysvetlenie: 18 je najmenšie možné číslo so súčtom číslic = 9 a celkovým číslicám = 2.
Vstup: S = 20 d = 3
Výstup: 299
Vysvetlenie: 299 je najmenšie možné číslo so súčtom číslic = 20 a celkovým číslicám = 3.
Vstup: S = 1 d = 1
Výstup: 1
Vysvetlenie: 1 je najmenšie možné číslo so súčtom číslic = 1 a celkovým číslicám = 1.

Tabuľka obsahu

[Brut -force prístup] Iterujte postupne - O (d*(10^d)) čas a O (1) priestor
[Očakávaný prístup] Použitie chamtivej techniky - o (d) čas a O (1) priestor

[Brut -force prístup] Iterujte postupne - O (d*(10^d)) čas a O (1) priestor

Pretože čísla sú sekvenčné prístup opakuje sa z najmenší číslo digitu do najväčší kontrola každého z nich. Pre každé číslo vypočítame súčet jeho číslic a vráťte prvú platnú zhodu, ktorá zaistí, že je vybrané najmenšie možné číslo. Ak neexistuje platné číslo, vrátime sa '-1' .

C++

// 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# 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));

Výstup

[Očakávaný prístup] Použitie chamtivej techniky - o (d) čas a O (1) priestor

Prístup zaisťuje číslicu vľavo je nenulová tak my rezerva 1 pre ňu a distribuovať zostávajúcu sumu z doprava doľava Vytvorenie najmenšieho možného čísla. Ten chamtivý prístup pomáha pri umiestňovaní najväčších možných hodnôt (do 9) na polohy na pravej strane Aby som udržal číslo malé.

Kroky na implementáciu vyššie uvedenej myšlienky:

Skontrolujte obmedzenia, aby ste zaistili a Platné súčty s môže byť vytvorený pomocou D číslice inak vrátiť sa '-1' .
Inicializovať vyplývať ako reťazec D '0's a rezerva 1 pre Zľavová číslica znížením s o 1 .
Prejsť doprava doľava a umiestniť najväčšia možná číslica (<= 9) pri aktualizácii siež preto.
Či siež<= 9 Umiestnite svoju hodnotu na aktuálnu pozíciu a nastavte s = 0 zastaviť ďalšie aktualizácie.
Priradiť Zľavová číslica pridaním zostávajúci s Aby sa zabezpečilo, že zostane nenulový .
Previesť vyplývať reťazec do požadovaného formátu a návrat Je to ako konečný výstup.

C++

// 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; }