C++ 通过在每个步骤中添加1或者A * 10^c来最小化将K从0转换为B的操作次数

给定整数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五次，得到1337 – 250 * 5即87。再次，我们可以从当前的b中减去3次a，得到12，通过减去一次可以将其减少到零，得到总步数20。

输入

int A = 70
int B = 700

输出结果

1

解释： 我们可以直接将a乘以10并从b中减去。

方法1

在这个方法中，我们首先创建一个函数，该函数以a和b作为参数，并返回所需的最小步骤作为返回值。

在函数中，我们将从b到0进行计算，以便于计算，而不是从使k为0到b。

首先，我们将创建一个变量来存储步骤，并将k设置为a。我们将使用while循环，直到b大于a为止。然后，我们将k设置为a，并将k乘以10，直到它大于b，然后我们将其除以10以获得比b小但在b之前的a的倍数，并从b中减去它并保持计数。

在for循环结束后，我们将b小于a，我们只能从中减去一个，并将该值添加到steps中，并将其返回以在主函数中打印。

示例

#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增加1，要么将给定的数字’A’乘以10的任意正次幂加到k上）来获取将整数k转换为b所需的最小步数。我们通过使用while循环实现了两种方法，它们的时间复杂度和空间复杂度都是常数。