Dado un número N , la tarea es encontrar el número mínimo de operaciones para convertir el entero dado en cualquier potencia de K donde en cada operación se puede eliminar cualquiera de los dígitos o se puede agregar cualquiera de los dígitos en la parte posterior del entero.
Ejemplos:
Entrada: N = 247, K = 3
Salida: 1
Explicación: En la 1ª operación se puede quitar el dígito 4. Por lo tanto, N = 27 que es una potencia de K.Entrada: N = 5, K = 2
Salida: 2
Explicación: En la primera operación, se puede quitar el dígito 5 y en la segunda operación, se puede agregar el dígito 2 al final. Por lo tanto, N = 2 que es una potencia de K.
Enfoque: El problema dado se puede resolver almacenando todas las potencias de K en un vector y calculando el número de operaciones requeridas para convertir el número entero N en la potencia actual. A continuación se detallan los pasos a seguir:
- Almacene todas las potencias de K en potencias vectoriales .
- Ahora recorra las potencias vectoriales y calcule el número de operaciones requeridas para convertir el número entero N dado en la potencia actual, lo que se puede hacer de la siguiente manera:
- Convierte los enteros dados en strings s1 y s2 .
- Inicialice dos variables i = 0 y j = 0 .
- Si s1[i] es igual a s2[j] , incremente tanto i como j . De lo contrario, incremente j solamente.
- El número requerido de operaciones será S1.longitud + S2.longitud – (2 * i) .
- Mantener el mínimo de las operaciones requeridas sobre todos los valores que es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
#define int long long
// Function to find all powers of
// K in the range [1, 10^18]
vector<int> findPowers(int K)
{
// Stores the powers of K
vector<int> powers;
int val = 1;
// Loop to iterate over all
// powers in the range
while (val <= 1e18) {
powers.push_back(val);
val *= K;
}
// Return answer
return powers;
}
// Function to find minimum operations to
// convert given integer into a power of K
int minOperations(int N, int K)
{
// Store all the powers of K
vector<int> powers = findPowers(K);
// Stores the final result
int res = INT_MAX;
// Loop to iterate through all
// the powers of K
for (int x = 0; x < powers.size(); x++) {
// Convert integers to strings
// for easier comparison
string s1 = to_string(powers[x]);
string s2 = to_string(N);
int i = 0, j = 0;
// Loop to calculate operations
// required to convert s1 to s2
while (i < s1.size() && j < s2.size()) {
// Count no of equal character
if (s1[i] == s2[j]) {
i++;
}
// Increment j by 1
j++;
}
// Update res
res = min(res,
(int)(s1.size()
+ s2.size() - 2 * i));
}
// Return answer;
return res;
}
// Driver Code
int32_t main()
{
int N = 247;
int K = 3;
cout << minOperations(N, K);
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG{
// Function to find all powers of
// K in the range [1, 10^18]
static Vector<Integer> findPowers(int K)
{
// Stores the powers of K
Vector<Integer> powers = new Vector<Integer>();
int val = 1;
// Loop to iterate over all
// powers in the range
while (val <= (int)(9999999999L)) {
powers.add(val);
val *= K;
}
// Return answer
return powers;
}
// Function to find minimum operations to
// convert given integer into a power of K
static int minOperations(int N, int K)
{
// Store all the powers of K
Vector<Integer> powers = findPowers(K);
// Stores the final result
int res = Integer.MAX_VALUE;
// Loop to iterate through all
// the powers of K
for (int x = 0; x < powers.size(); x++) {
// Convert integers to Strings
// for easier comparison
String s1 = String.valueOf(powers.get(x));
String s2 = String.valueOf(N);
int i = 0, j = 0;
// Loop to calculate operations
// required to convert s1 to s2
while (i < s1.length() && j < s2.length()) {
// Count no of equal character
if (s1.charAt(i) == s2.charAt(j)) {
i++;
}
// Increment j by 1
j++;
}
// Update res
res = Math.min(res,
(int)(s1.length()
+ s2.length() - 2 * i));
}
// Return answer;
return res;
}
// Driver Code
public static void main(String[] args)
{
int N = 247;
int K = 3;
System.out.print(minOperations(N, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 code for the above approach import sys # Function to find all powers of # K in the range [1, 10^18] def findPowers(K): # Stores the powers of K powers = [] val = 1 # Loop to iterate over all # powers in the range while (val <= 1e18): powers.append(val) val *= K # Return answer return powers # Function to find minimum operations to # convert given integer into a power of K def minOperations(N, K): # Store all the powers of K powers = findPowers(K) # Stores the final result res = sys.maxsize # Loop to iterate through all # the powers of K for x in range(len(powers)): # Convert integers to strings # for easier comparison s1 = str(powers[x]) s2 = str(N) i = 0 j = 0 # Loop to calculate operations # required to convert s1 to s2 while (i < len(s1) and j < len(s2)): # Count no of equal character if (s1[i] == s2[j]): i += 1 # Increment j by 1 j += 1 # Update res res = min(res, (int)(len(s1) + len(s2) - 2 * i)) # Return answer; return res # Driver Code if __name__ == "__main__": N = 247 K = 3 print(minOperations(N, K)) # This code is contributed by ukasp.
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find all powers of
// K in the range [1, 10^18]
static List<int> findPowers(int K)
{
// Stores the powers of K
List<int> powers = new List<int>();
int val = 1;
// Loop to iterate over all
// powers in the range
while (val <= ((int)(999999999))) {
powers.Add(val);
val *= K;
}
// Return answer
return powers;
}
// Function to find minimum operations to
// convert given integer into a power of K
static int minOperations(int N, int K)
{
// Store all the powers of K
List<int> powers = findPowers(K);
// Stores the readonly result
int res = int.MaxValue;
// Loop to iterate through all
// the powers of K
for (int x = 0; x < powers.Count; x++) {
// Convert integers to Strings
// for easier comparison
String s1 = String.Join("",powers[x]);
String s2 = String.Join("",N);
int i = 0, j = 0;
// Loop to calculate operations
// required to convert s1 to s2
while (i < s1.Length && j < s2.Length) {
// Count no of equal character
if (s1[i] == s2[j]) {
i++;
}
// Increment j by 1
j++;
}
// Update res
res = Math.Min(res,
(int)(s1.Length
+ s2.Length - 2 * i));
}
// Return answer;
return res;
}
// Driver Code
public static void Main(String[] args)
{
int N = 247;
int K = 3;
Console.Write(minOperations(N, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Python 3 code for the above approach
// Function to find all powers of
// K in the range [1, 10^18]
function findPowers(K){
// Stores the powers of K
var powers = []
var val = 1
// Loop to iterate over all
// powers in the range
while (val <= 1e18){
powers.push(val)
val *= K
}
// Return answer
return powers
}
// Function to find minimum operations to
// convert given integer into a power of K
function minOperations(N, K){
// Store all the powers of K
var powers = findPowers(K)
// Stores the final result
var res = 99999999999;
// Loop to iterate through all
// the powers of K
for(var x = 0; x < powers.length;x++){
// Convert integers to strings
// for easier comparison
var s1 = (powers[x].toString());
var s2 = (N.toString());
var i = 0
var j = 0
// Loop to calculate operations
// required to convert s1 to s2
while (i < s1.length && j < s2.length){
// Count no of equal character
if (s1[i] == s2[j]){
i += 1
}
// Increment j by 1
j += 1
}
// Update res
res = Math.min(res,
(s1.length
+ s2.length - 2 * i))
}
// Return answer;
return res
}
// Driver Code
N = 247
K = 3
document.write(minOperations(N, K));
// This code is contributed by 29AjayKumar
</script>
Producción
1
Complejidad de Tiempo: O((log N) 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA