logo

TechCodeview

指定された数字カウントと合計を備えた最小数

GFG練習で試してみてください ' title=

2つの整数が与えられます s そして d を見つけます 最小 正確にある可能性のある数 D桁 そしてa 数字の合計 に等しい s 。
番号をaとして返します 弦 。そのような数が存在しない場合 '-1' 。

優先キューJava

例：



入力： 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）スペース

数字はシーケンシャルであるため ブルートフォースアプローチ から繰り返します 最小 d-digit番号 最大 それぞれをチェックします。数ごとに計算します その数字の合計 そして、可能な限り最小の数値が選択されるようにする最初の有効な一致を返します。有効な番号が存在しない場合、返します '-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# 
// 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));

出力 
18

[期待されるアプローチ]貪欲なテクニックの使用-O（d）時間とO（1）スペース

このアプローチにより、左端の数字が保証されます ゼロ以外です だから私たち 予約1 そのために、残りの合計をから分配します 右から左 可能な限り最小の数を形成します。 貪欲なアプローチ 可能な最大の値（最大9）をに配置するのに役立ちます 右端の位置 数を小さく保つため。



上記のアイデアを実装する手順：

  • 制約を確認して、a 有効な合計 使用して形成できます D桁 それ以外の場合は戻ります '-1' 。
  • 初期化 結果 一連の文字列として d '0 そして 予約1 のために 左桁 減らすことによって s by 1 。
  • からのトラバース 右から左 と配置します 可能な最大の数字（<= 9) 更新中 s それに応じて。
  • もし s<= 9 その価値を現在の位置に置き、設定します S = 0 さらに更新を停止します。
  • を割り当てます 左桁 を追加して 残りのs それが残ることを確認するため ゼロ以外 。
  • 変換します 結果 必要な形式への文字列と 戻る 最終出力として。
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; }
Java 
// 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 
# 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# 
// 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 
// 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