最小化将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中减去5次A * 10，得到1337 - 250 * 5，即87。再次，我们可以从当前b中减去3次a，得到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以获得小于b的a的倍数，并从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 
   // getting the largest value of A * 10^p less than equals to B
   while(b >= a){
      k = a; // assigning k the value of a 
      while(k <= b){
         k *= 10;
      }      
      k /= 10; // removing the extra value of 10 factor 
      b -= k;
      steps++;
   }
   // now value of b is less than a so we just have to increment the k or decrease the b by 1 at each step
   steps += b; 
   return steps; // return the final answer 
}

int main(){
   int a = 25; // given number
   int b = 1337 ; // given target
   cout<<"The minimum number of steps required to convert K to B is "<<getSteps(a, b)<<endl;
   return 0; 
}

输出

The minimum number of steps required to convert K to B is 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; // variable to work with later
   int steps = 0; // variable to store the steps 
   k = a; // assigning k value of a 
   // get the maximum multiple of a which is less than or equals to b
   while (k <= b) {
      k = k * 10;
   }
   // we need less or equal number 
   k /= 10;
   steps = b % a;
   // subtracting the value of steps from b as we are going to add one by one to achieve this also now b will be the multiple of a 
   b = b - b %a; 
   // reduce the k to make it less than a 
   while (k >= a) {
      steps = steps + b / k;
      b = b %k;
      k = k / 10;
   }
   return steps; // return the final answer 
}
int main(){
   int a = 25; // given number
   int b = 1337 ; // given target
   cout<<"The minimum number of steps required to convert K to B is "<<getSteps(a, b)<<endl;
   return 0; 
}

输出

The minimum number of steps required to convert K to B is 20

时间和空间复杂度

上述代码的时间复杂度是常数或O(1)。

上述代码的空间复杂度为O(1)，因为我们这里没有使用任何额外的空间。

结论

在本教程中，我们实现了一个程序，用于获取将整数k转换为b所需的最小步骤数，通过执行两个给定的任务，即要么将k加1，要么将给定数字'A'乘以10的任意正幂加到k上。我们实现了两种方法，这两种方法都具有常数时间和空间复杂度，通过使用while循环。