最小化将 K 从 0 转换为 B 的运算次数，每一步加 1 或加 A * 10^c
给定一个整数 B 和 A，我们需要通过应用给定的运算，以最少的步骤将 K 从 0 转换为 B。
我们可以将当前数字 K 加 1，即 K = K + 1
我们可以将数字 A 与 10 的任意幂的乘积加到数字 K 上，即 K = K + A * 10^p，其中 p 为任意非负数。
示例
输入
int A = 25 int B = 1337
输出
20
解释:我们可以将 b 中的值 A * 10 减 5 次，得到 1337 - 250 * 5，即 87。同样，我们可以将当前 b 中的值 A * 10 减 3 次，得到 12，减 1 次即可将其归零，总步数为 20。
输入
int A = 70 int B = 700
输出
1
解释:我们可以直接将 a 乘以 10，然后将其从 b 中减去。
方法 1
在此方法中，我们首先创建一个函数，该函数同时接受 a 和 b 作为参数，并返回所需的最小步数作为返回值。
在函数中，为了便于计算，我们将从 b 递增到 0，而不是从 k 递增到 b。
首先，我们将创建一个变量来存储步数，并使 k 等于 a。我们将使用 while 循环，直到 b 大于 a。然后，我们使 k 等于 a，并将 k 乘以 10，直到它大于 b，然后将其除以 10，得到 a 的倍数，该倍数恰好小于 b，并从 b 中减去该倍数并保持计数。
for 循环结束后，b 小于 a，我们只能从中减 1，并将该值添加到步数中，然后返回以在主函数中打印。
示例
#include <bits/stdc++.h>
using namespace std;
int getSteps(int a, int b){
int k = 0;
int steps = 0; // variable to store the steps
// 获取小于等于 B 的 A * 10^p 的最大值
while(b >= a){
k = a; // 将 a 的值赋给 k
while(k <= b){
k *= 10;
}
k /= 10; // 移除多余的因子 10
b -= k;
steps++;
}
// 现在 b 的值小于 a，因此我们只需在每一步增加 k 或将 b 减 1
steps += b;
return steps; // 返回最终答案
}
int main(){
int a = 25; // 给定数字
int b = 1337; // 给定目标
cout<<"将 K 转换为 B 所需的最少步骤数是 "<<getSteps(a, b)<<endl;
return 0;
}
输出
将 K 转换为 B 所需的最少步骤数是 20
时间和空间复杂度
上述代码的时间复杂度为常数，即 O(1)，因为我们从给定数字中减去 10 的乘积，这意味着即使对于整数最大值，我们也只需要很少的迭代次数。
由于我们这里没有使用任何额外的空间，因此上述代码的空间复杂度为 O(1) 或常数。
方法 2
这种方法与前一种方法略有不同，它基于数学概念 b = x * a + r，其中 x 和 r 为非负数，我们将从 b 中约去 a 的因数来得到答案。
示例
#include <bits/stdc++.h>
using namespace std;
int getSteps(int a, int b){
int k; // 稍后使用的变量
int steps = 0; // 存储步数的变量
k = a; // 将 k 赋给 a
// 获取小于或等于 b 的最大 a 倍数
while (k <= b) {
k = k * 10;
}
// 我们需要小于或等于 b 的数
k /= 10;
steps = b % a;
// 从 b 中减去 steps 的值，因为我们将逐一相加来实现这一点，现在 b 也是 a 的倍数
b = b - b %a;
// 减小 k 使其小于 a
while (k >= a) {
steps = steps + b / k;
b = b %k;
k = k / 10;
}
return steps; // 返回最终答案
}
int main(){
int a = 25; // 给定数字
int b = 1337; // 给定目标
cout<<"将 K 转换为 B 所需的最少步骤数是 "<<getSteps(a, b)<<endl;
return 0;
}
输出
将 K 转换为 B 所需的最少步骤数是 20
时间和空间复杂度
上述代码的时间复杂度为常数，即 O(1)。
上述代码的空间复杂度为 O(1)，因为我们这里没有使用任何额外的空间。
结论
在本教程中，我们实现了一个程序，通过执行给定的两个任务来获取将整数 k 转换为 b 所需的最小步数。这两个任务是将 k 加 1，或者将给定数字"A"乘以 10 的任意正幂后加到 k 上。我们使用 while 循环实现了这两种方法，它们都具有常数时间和空间复杂度。
