DET MINSTA ANTALET MED GIVET SIFFRA RÄKNING OCH SUMMA

Prova det på GFG -praxis ' title=

Ges två heltal s och d hitta minsta Möjligt nummer som har exakt D -siffror och en summan av siffror lika med s .
Returnera numret som en sträng . Om det inte finns något sådant nummer '-1' .

Exempel:

Input: S = 9 D = 2
Produktion: 18
Förklaring: 18 är det minsta möjliga antalet med summan av siffror = 9 och totala siffror = 2.
innehåller delsträng java
Input: s = 20 d = 3
Produktion: 299
Förklaring: 299 är det minsta möjliga antalet med summan av siffror = 20 och totala siffror = 3.
Input: s = 1 d = 1
Produktion: 1
Förklaring: 1 är det minsta möjliga antalet med summan av siffror = 1 och totala siffror = 1.

Innehållsbord

java bubbla sortera

[Brute -force -strategi] iterera sekventiellt - o (d*(10^d)) tid och o (1) utrymme
[Förväntat tillvägagångssätt] Med hjälp av girig teknik - O (D) Tid och O (1) Rymdutrymme

[Brute -force -strategi] iterera sekventiellt - o (d*(10^d)) tid och o (1) utrymme

Eftersom siffror är sekventiella brute force -strategi iterater från minsta D-siffrigt nummer till största Kontrollera var och en. För varje nummer beräknar vi summan av dess siffror och returnera den första giltiga matchen och säkerställa att det minsta möjliga numret är valt. Om det inte finns något giltigt nummer '-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));

Produktion

[Förväntat tillvägagångssätt] Med hjälp av girig teknik - O (D) Tid och O (1) Rymdutrymme

Tillvägagångssättet säkerställer den vänstra siffran är icke-noll Så vi reservera 1 för det och distribuera den återstående summan från höger till vänster för att bilda det minsta möjliga antalet. De girig inställning hjälper till att placera största möjliga värden (upp till 9) vid högsta positioner för att hålla antalet litet.

typgjutning och typkonvertering i java

Steg för att genomföra ovanstående idé:

Kontrollera begränsningar för att säkerställa en giltig summa S kan bildas med D -siffror annars återvänder '-1' .
Initiera resultat som en sträng av d '0's och reservera 1 för längst till vänster genom att minska s av 1 .
Travera från höger till vänster och placera största möjliga siffra (<= 9) Under uppdateringen s följaktligen.
Om s<= 9 placera sitt värde i den nuvarande positionen och set s = 0 för att stoppa ytterligare uppdateringar.
Tilldela längst till vänster genom att lägga till återstående S för att säkerställa att det kvarstår icke-noll .
Konvertera resultat sträng till önskat format och återvända det som den slutliga utgången.

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