算法题（大于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# 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

输出如下：