最小化將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迴圈。