算法题：大于Y且数字总和等于X的最小数字

本文概述

• C ++
• C#

给定两个整数X和ÿ, 找到具有数字总和的最小数字X, 严格大于ÿ.

例子：

输入：X = 18, Y = 99
输出：189说明：189是大于99的最小数字, 且位数总和=18。
输入：X = 12, Y = 72
输出：75
说明：75是大于的最小数字72的数字总和= 12。

天真的方法：天真的方法是从Y + 1并检查是否有任何数字的总和是X或不。如果找到任何这样的数字, 请打印该数字。

时间复杂度:O((R - Y)*log10N)，其中R为迭代到的最大数字，N为[Y, R]范围内的数字

高效方法：这个想法是遍历数字ÿ从右到左, 并尝试增加当前数字并向右更改数字, 以使数字总和等于X。步骤如下：

• 如果我们考虑从右数起的第(k + 1)位，并将其递增，那么k个最小有效数字的和有可能是[0,9k]范围内的任何数字。
• 找到这样的位置后, 请停止该过程并在该迭代中打印该数字。
• 如果k个最小有效数字有和M(其中0≤M≤9k)，则贪婪地得到答案:
  • 从右向左遍历并插入9, 然后从数字总和中减去9。
  • 一次, 总和小于9, 放置剩余的总和。

下面是上述方法的实现：

C ++

//C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
//Function to return the minimum string
//of length d having the sum of digits s
string helper( int d, int s)
{
 
     //Return a string of length d
     string ans(d, '0' );
 
     for ( int i = d - 1; i>= 0; i--) {
 
         //Greedily put 9's in the end
         if (s>= 9) {
             ans[i] = '9' ;
             s -= 9;
         }
 
         //Put remaining sum
         else {
             char c = ( char )s + '0' ;
             ans[i] = c;
             s = 0;
         }
     }
 
     return ans;
}
 
//Function to find the smallest
//number greater than Y
//whose sum of digits is X
string findMin( int x, int Y)
{
 
     //Convert number y to string
     string y = to_string(Y);
 
     int n = y.size();
     vector<int> p(n);
 
     //Maintain prefix sum of digits
     for ( int i = 0; i <n; i++) {
         p[i] = y[i] - '0' ;
         if (i> 0)
             p[i] += p[i - 1];
     }
 
     //Iterate over Y from the back where
     //k is current length of suffix
     for ( int i = n - 1, k = 0;; i--, k++) {
 
         //Stores current digit
         int d = 0;
 
         if (i>= 0)
             d = y[i] - '0' ;
 
         //Increase current digit
         for ( int j = d + 1; j <= 9; j++) {
 
             //Sum upto current prefix
             int r = (i> 0) * p[i - 1] + j;
 
             //Return answer if remaining
             //sum can be obtained in suffix
             if (x - r>= 0 and x - r <= 9 * k) {
 
                 //Find suffix of length k
                 //having sum of digits x-r
                 string suf = helper(k, x - r);
 
                 string pre = "" ;
                 if (i> 0)
                     pre = y.substr(0, i);
 
                 //Append current character
                 char cur = ( char )j + '0' ;
                 pre += cur;
 
                 //Return the result
                 return pre + suf;
             }
         }
     }
}
 
//Driver Code
int main()
{
     //Given Number and Sum
     int x = 18;
     int y = 99;
 
     //Function Call
     cout <<findMin(x, y) <<endl;
     return 0;
}

C#

//C# program for the above approach
using System;
using System.Text;
using System.Collections;
 
class GFG{
 
//Function to return the minimum string
//of length d having the sum of digits s
static string helper( int d, int s)
{
 
     //Return a string of length d
     StringBuilder ans = new StringBuilder();
     
     for ( int i = 0; i <d; i++)
     {
         ans.Append( "0" );
     }
     
     for ( int i = d - 1; i>= 0; i--)
     {
         
         //Greedily put 9's in the end
         if (s>= 9)
         {
             ans[i] = '9' ;
             s -= 9;
         }
         
         //Put remaining sum
         else
         {
             char c = ( char )(s + ( int ) '0' );
             ans[i] = c;
             s = 0;
         }
     }
     return ans.ToString();
}
 
//Function to find the smallest
//number greater than Y
//whose sum of digits is X
static string findMin( int x, int Y)
{
     
     //Convert number y to string
     string y = Y.ToString();
     
     int n = y.Length;
     
     ArrayList p = new ArrayList();
     
     for ( int i = 0; i <n; i++)
     {
         p.Add(0);
     }
     
     //Maintain prefix sum of digits
     for ( int i = 0; i <n; i++)
     {
         p[i] = ( int )(( int ) y[i] - ( int ) '0' );
         
         if (i> 0)
         {
             p[i] = ( int )p[i] +
                    ( int )p[i - 1];
         }
     }
     
     //Iterate over Y from the back where
     //k is current length of suffix
     for ( int i = n - 1, k = 0;; i--, k++)
     {
         
         //Stores current digit
         int d = 0;
         
         if (i>= 0)
         {
             d = ( int ) y[i] - ( int ) '0' ;
         }
         
         //Increase current digit
         for ( int j = d + 1; j <= 9; j++)
         {
             int r = j;
             
             //Sum upto current prefix
             if (i> 0)
             {
                 r += ( int ) p[i - 1];
             }
             
             //Return answer if remaining
             //sum can be obtained in suffix
             if (x - r>= 0 && x - r <= 9 * k)
             {
                 
                 //Find suffix of length k
                 //having sum of digits x-r
                 string suf = helper(k, x - r);
                 
                 string pre = "" ;
                 
                 if (i> 0)
                     pre = y.Substring(0, i);
                 
                 //Append current character
                 char cur = ( char )(j + ( int ) '0' );
                 pre += cur;
                 
                 //Return the result
                 return pre + suf;
             }
         }
     }
}
 
//Driver code
public static void Main( string [] arg)
{
     
     //Given number and sum
     int x = 18;
     int y = 99;
     
     //Function call
     Console.Write(findMin(x, y));
}
}
 
//This code is contributed by rutvik_56

输出如下：

189

时间复杂度:O (log10Y)

辅助空间:O (log10Y)

---