本文概述
- C ++
- C#
例子:
输入:X = 18, Y = 99天真的方法:天真的方法是从Y + 1并检查是否有任何数字的总和是X或不。如果找到任何这样的数字, 请打印该数字。
输出:189说明:189是大于99的最小数字, 且位数总和=18。
输入:X = 12, Y = 72
输出:75
说明:75是大于的最小数字72的数字总和= 12。
时间复杂度: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)
【算法题(大于Y且数字总和等于X的最小数字)】辅助空间:O (log10Y)
推荐阅读
- 算法题(整数流中的中位数(运行的整数))
- JavaScript数学对象Math完整参考
- 如何使用Python在OpenCV中读取图像(代码实现)
- CSS如何使用3D变换(代码示例)
- 在只允许使用2位数字(4和7)的序列中查找第n个元素|S2 (log(n)方法)
- Western Digital面向经验分享| FTE招聘校园
- 如何从给定的C/C++程序中删除注释()
- Android Intent实现界面跳转切换,随时记录一下
- android的service