Minimice las operaciones para convertir K de 0 a B agregando 1 o A * 10^c en cada paso

Dados tres números A, B y K donde K es 0 inicialmente. La tarea es encontrar las operaciones mínimas para convertir K en B usando las siguientes operaciones:

• Agregue 1 a K , es decir, K = K + 1
• Agregue A * 10 ^c en K , es decir, K = K + A * 10 ^c , donde c es cualquier número entero ( c >= 0 ).

Ejemplos :

Entrada: A = 2, B = 7
Salida: 4
Explicación: Inicialmente K = 0, las siguientes operaciones se realizan en K:

1. K = K + A * 10 ⁰ => K = 0 + 2 * 1 => K= 2
2. K = K + A * 10 ⁰ => K = 2 + 2 * 1 => K= 4
3. K = K + A * 10 ⁰ => K = 4 + 2 * 1 => K= 6
4. Añadir 1 a K => K = 7

Por lo tanto, las operaciones mínimas necesarias son 4

Entrada: A = 25, B = 1337
Salida: 20

Enfoque : un número se puede representar como B = X * A + Y , donde A es el número máximo que se multiplica con X y su producto es el más cercano a B e Y es el número que es menor que A. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable K y asígnele X.
• Multiplica K por 10 hasta que sea mayor que B .
• Inicialice la variable ans con 0.
• Almacene la parte Y en ans usando el operador de módulo ans = B % A .
• Y restando ans de B digamos B = B – ans .
• Ahora módulo B por K hasta que sea K es mayor o igual a A.
• Y tienda de división de B/K en ans.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum operations
int minOperations(int A, int B)
{
 
    // Initialize K and assign A into K
    int K = A;
 
    // Calculate the nearest
    // smaller number with B
    while (K < B) {
        K = K * 10;
        // If K is larger than B divide
        // by 10 and break the loop
        // We can get the nearest number
        if (K > B) {
            K = K / 10;
            break;
        }
    }
 
    // Now according to approach
    // Y part is B % A
    // which is smaller than X
    int ans = B % A;
 
    // Subtract Y part from B
    B = B - ans;
 
    // Iterate until K is
    // Greater than or equal to A
    while (K >= A) {
 
        // store ans which is division number
        ans = ans + B / K;
 
        // Modulus B by K
        B = B % K;
 
        // Divide K by 10
        K = K / 10;
    }
    return ans;
}
 
// Driver Code
int main()
{
 
    int A = 25, B = 1337;
    int ans = minOperations(A, B);
    cout << ans;
    return 0;
}

// Java code for the above approach
import java.util.*;
 
class GFG{
 
  // Function to find the minimum operations
  static int minOperations(int A, int B)
  {
 
    // Initialize K and assign A into K
    int K = A;
 
    // Calculate the nearest
    // smaller number with B
    while (K < B) {
      K = K * 10;
      // If K is larger than B divide
      // by 10 and break the loop
      // We can get the nearest number
      if (K > B) {
        K = K / 10;
        break;
      }
    }
 
    // Now according to approach
    // Y part is B % A
    // which is smaller than X
    int ans = B % A;
 
    // Subtract Y part from B
    B = B - ans;
 
    // Iterate until K is
    // Greater than or equal to A
    while (K >= A) {
 
      // store ans which is division number
      ans = ans + B / K;
 
      // Modulus B by K
      B = B % K;
 
      // Divide K by 10
      K = K / 10;
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int A = 25, B = 1337;
    int ans = minOperations(A, B);
    System.out.print(ans);
  }
}
 
// This code is contributed by sanjoy_62.

# Python program for the above approach
 
# Function to find the minimum operations
def minOperations(A, B):
 
    # Initialize K and assign A into K
    K = A
 
    # Calculate the nearest
    # smaller number with B
    while (K < B):
         
        K = K * 10
        # If K is larger than B divide
        # by 10 and break the loop
        # We can get the nearest number
        if (K > B):
            K = K // 10
            break
 
    # Now according to approach
    # Y part is B % A
    # which is smaller than X
    ans = B % A
 
    # Subtract Y part from B
    B = B - ans
 
    # Iterate until K is
    # Greater than or equal to A
    while (K >= A):
 
        # store ans which is division number
        ans = ans + B // K
 
        # Modulus B by K
        B = B % K
 
        # Divide K by 10
        K = K // 10
 
    return ans
 
# Driver Code
A = 25
B = 1337
ans = minOperations(A, B)
print(ans)
    
# This code is contributed by Samim Hossain Mondal.

// C# code for the above approach
using System;
class GFG
{
 
  // Function to find the minimum operations
  static int minOperations(int A, int B)
  {
 
    // Initialize K and assign A into K
    int K = A;
 
    // Calculate the nearest
    // smaller number with B
    while (K < B)
    {
      K = K * 10;
       
      // If K is larger than B divide
      // by 10 and break the loop
      // We can get the nearest number
      if (K > B)
      {
        K = K / 10;
        break;
      }
    }
 
    // Now according to approach
    // Y part is B % A
    // which is smaller than X
    int ans = B % A;
 
    // Subtract Y part from B
    B = B - ans;
 
    // Iterate until K is
    // Greater than or equal to A
    while (K >= A)
    {
 
      // store ans which is division number
      ans = ans + B / K;
 
      // Modulus B by K
      B = B % K;
 
      // Divide K by 10
      K = K / 10;
    }
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    int A = 25, B = 1337;
    int ans = minOperations(A, B);
    Console.Write(ans);
  }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
    // JavaScrip tprogram for the above approach
 
    // Function to find the minimum operations
    const minOperations = (A, B) => {
 
        // Initialize K and assign A into K
        let K = A;
 
        // Calculate the nearest
        // smaller number with B
        while (K < B) {
            K = K * 10;
            // If K is larger than B divide
            // by 10 and break the loop
            // We can get the nearest number
            if (K > B) {
                K = parseInt(K / 10);
                break;
            }
        }
 
        // Now according to approach
        // Y part is B % A
        // which is smaller than X
        let ans = B % A;
 
        // Subtract Y part from B
        B = B - ans;
 
        // Iterate until K is
        // Greater than or equal to A
        while (K >= A) {
 
            // store ans which is division number
            ans = ans + parseInt(B / K);
 
            // Modulus B by K
            B = B % K;
 
            // Divide K by 10
            K = parseInt(K / 10);
        }
        return ans;
    }
 
    // Driver Code
    let A = 25, B = 1337;
    let ans = minOperations(A, B);
    document.write(ans);
 
// This code is contributed by rakeshsahni
 
</script>

20

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)