LE PLUS PETIT NOMBRE AVEC LE NOMBRE DE CHIFFRES ET LA SOMME DONNÉS

Essayez-le sur GFG Practice ' title=

Étant donné deux entiers s et d trouver le le plus petit nombre possible qui a exactement D chiffres et un somme de chiffres égal à s .
Renvoie le numéro en tant que chaîne . Si aucun nombre n'existe, retourne '-1' .

Exemples:

Saisir: s = 9 d = 2
Sortir: 18
Explication: 18 est le plus petit nombre possible avec la somme des chiffres = 9 et les chiffres totaux = 2.
Saisir: s = 20 d = 3
Sortir: 299
Explication: 299 est le plus petit nombre possible avec la somme des chiffres = 20 et les chiffres totaux = 3.
Saisir: s = 1 d = 1
Sortir: 1
Explication: 1 est le plus petit nombre possible avec la somme des chiffres = 1 et les chiffres totaux = 1.

Tableau de contenu

[Approche de force brute] Itérer séquentiellement - o (d * (10 ^ d)) et o (1) espace
[Approche attendue] Utilisation de la technique gourmande - O (d) Temps et O (1) Espace

[Approche de force brute] Itérer séquentiellement - o (d * (10 ^ d)) et o (1) espace

Puisque les nombres sont séquentiels, approche de la force brute itérer du le plus petit Numéro de chiffre à D au le plus grand vérifier chacun. Pour chaque nombre, nous calculons le somme de ses chiffres et renvoyer la première correspondance valide garantissant le plus petit numéro possible. Si aucun nombre valide n'existe, nous retournons '-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));

Sortir

[Approche attendue] Utilisation de la technique gourmande - O (d) Temps et O (1) Espace

L'approche assure le chiffre le plus à gauche est non nul Alors nous réserve 1 pour cela et distribuer la somme restante de De la droite à gauche pour former le plus petit numéro possible. Le approche gourmand aide à placer les valeurs les plus importantes possibles (jusqu'à 9) positions les plus à droite Pour garder le nombre petit.

Étapes pour mettre en œuvre l'idée ci-dessus:

Vérifiez les contraintes pour assurer un somme valide s peut être formé en utilisant D chiffres Sinon Retour '-1' .
Initialiser résultat comme une chaîne de D '0 et réserve 1 pour chiffre le plus à gauche en réduisant s par 1 .
Traverser de De la droite à gauche et placer le le plus grand chiffre possible (<= 9) Lors de la mise à jour s par conséquent.
Si s<= 9 Placer sa valeur à la position actuelle et définir S = 0 pour arrêter d'autres mises à jour.
Attribuer le chiffre le plus à gauche en ajoutant le restant Pour s'assurer qu'il reste non nul .
Convertir le résultat chaîne au format requis et retour il est la sortie finale.

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