Encuentre K que requiera incrementos o decrementos mínimos de los elementos de la array para obtener una secuencia de potencias crecientes de K

Dada una array que consta de N enteros, la tarea es encontrar el entero K que requiere el número mínimo de movimientos para convertir la array dada en una secuencia de potencias de K, es decir, {K ⁰ , K ¹ , K ² , ……. , K ^{N – 1} } . En cada movimiento, aumente o disminuya un elemento de la array en uno.

Ejemplos:

Entrada: arr[] = {1, 2, 3}
Salida: 2
Explicación: Al incrementar arr[2] en 1 se modifica a {1, 2, 4} que es igual a {2 ⁰ , 2 ¹ , 2 ² }. Por lo tanto, K = 2.

Entrada: arr[] = {1, 9, 27}
Salida: 5
Explicación: Modificar la array a {1, 5, 25} requiere un número mínimo de movimientos. Por lo tanto, K = 5.

Enfoque: La idea es verificar todos los números a partir de 1 hasta que la potencia de un número cruce el valor máximo, es decir, 10 ¹⁰ (supuesto). Siga los pasos a continuación para resolver el problema:

1. Verifique todos los números del 1 al x hasta que el valor de x ^{N – 1}    < max_element of array + movimiento necesario para convertir en la potencia de 1 .
2. Cuente los movimientos necesarios para hacer una array en el poder de ese elemento.
3. Si el movimiento necesario es mínimo que el valor anterior, actualice el valor de K y movimientos mínimos .
4. Imprime el valor de K.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
// Function to find the value of K such
// that it takes minimum number of moves
// to convert the array in its power
ll findMinCostInteger(vector<ll>& a)
{
 
    // Size of the array
    int n = a.size();
 
    // Finding the sum of the array
    ll sum = accumulate(a.begin(),
                        a.end(), 0);
 
    ll K = 0, minmove = LLONG_MAX;
 
    // Find K for which the count
    // of moves will become minimum
    for (int i = 1;; ++i) {
 
        ll power = 1, count = 0;
 
        for (ll j = 0; j < n; ++j) {
 
            count += abs(a[j] - power);
            if (j != n - 1)
                power = power * (ll)i;
 
            // If exceeds maximum value
            if (power >= 1e10)
                break;
        }
 
        if (power >= (1e10)
            || power > (ll)(sum - n)
                           + a[n - 1])
            break;
 
        // Update minimum moves
        if (minmove > count) {
            minmove = count;
            K = i;
        }
    }
 
    // Print K corresponds to minimum
    // number of moves
    cout << K;
}
 
// Driver Code
int main()
{
 
    // Given vector
    vector<ll> a = { 1, 9, 27 };
 
    // Function Call
    findMinCostInteger(a);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
   
// Function to find the value of K such
// that it takes minimum number of moves
// to convert the array in its power
static void findMinCostInteger(int a[], int n)
{
     
    // Finding the sum of the array
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += a[i];
 
    int K = 0, minmove = Integer.MAX_VALUE;
 
    // Find K for which the count
    // of moves will become minimum
    for(int i = 1;; ++i)
    {
        int power = 1, count = 0;
         
        for(int j = 0; j < n; ++j)
        {
            count += Math.abs(a[j] - power);
             
            if (j != n - 1)
                power = power * i;
             
            // If exceeds maximum value
            if (power >= 1e10)
                break;
        }
         
        if (power >= (1e10) ||
            power > (sum - n) + a[n - 1])
            break;
         
        // Update minimum moves
        if (minmove > count)
        {
            minmove = count;
            K = i;
        }
    }
     
    // Print K corresponds to minimum
    // number of moves
    System.out.println(K);
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given vector
    int []a = { 1, 9, 27 };
 
    // Function Call
    findMinCostInteger(a, 3);
}
}
 
// This code is contributed by bgangwar59

# Python3 program for the above approach
import sys
 
# Function to find the value of K such
# that it takes minimum number of moves
# to convert the array in its power
def findMinCostInteger(a):
     
    # Size of the array
    n = len(a)
 
    # Finding the sum of the array
    sm = sum(a)
 
    K = 0
    minmove = sys.maxsize
 
    # Find K for which the count
    # of moves will become minimum
    i = 1
    while(1):
        power = 1
        count = 0
        for j in range(n):
            count += abs(a[j] - power)
             
            if (j != n - 1):
                power = power * i
 
            # If exceeds maximum value
            if (power >= 1e10):
                break
 
        if (power >= (1e10) or
            power > (sm - n) + a[n - 1]):
            break
 
        # Update minimum moves
        if (minmove > count):
            minmove = count
            K = i
             
        i += 1
 
    # Print K corresponds to minimum
    # number of moves
    print(K)
 
# Driver Code
if __name__ == '__main__':
     
    # Given vector
    a =  [ 1, 9, 27 ]
 
    # Function Call
    findMinCostInteger(a)
     
# This code is contributed by SURENDRA_GANGWAR

// C# program for the
// above approach
using System;
class GFG{
   
// Function to find the value
// of K such that it takes
// minimum number of moves
// to convert the array in
// its power
static void findMinCostint(int []a,
                           int n)
{   
  // Finding the sum of the array
  int sum = 0;
   
  for(int i = 0; i < n; i++)
    sum += a[i];
 
  int K = 0, minmove = int.MaxValue;
 
  // Find K for which the count
  // of moves will become minimum
  for(int i = 1;; ++i)
  {
    int power = 1, count = 0;
 
    for(int j = 0; j < n; ++j)
    {
      count += Math.Abs(a[j] - power);
 
      if (j != n - 1)
        power = power * i;
 
      // If exceeds maximum value
      if (power >= 1e10)
        break;
    }
 
    if (power >= (1e10) ||
        power > (sum - n) +
                 a[n - 1])
      break;
 
    // Update minimum moves
    if (minmove > count)
    {
      minmove = count;
      K = i;
    }
  }
 
  // Print K corresponds to
  // minimum number of moves
  Console.WriteLine(K);
}
 
// Driver Code
public static void Main(String []args)
{   
  // Given vector
  int []a = {1, 9, 27};
 
  // Function Call
  findMinCostint(a, 3);
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program for the above approach
 
// Function to find the value of K such
// that it takes minimum number of moves
// to convert the array in its power
function findMinCostLeteger(a, n)
{
      
    // Finding the sum of the array
    let sum = 0;
    for(let i = 0; i < n; i++)
        sum += a[i];
  
    let K = 0, minmove = Number.MAX_VALUE;
  
    // Find K for which the count
    // of moves will become minimum
    for(let i = 1;; ++i)
    {
        let power = 1, count = 0;
          
        for(let j = 0; j < n; ++j)
        {
            count += Math.abs(a[j] - power);
              
            if (j != n - 1)
                power = power * i;
              
            // If exceeds maximum value
            if (power >= 1e10)
                break;
        }
          
        if (power >= (1e10) ||
            power > (sum - n) + a[n - 1])
            break;
          
        // Update minimum moves
        if (minmove > count)
        {
            minmove = count;
            K = i;
        }
    }
      
    // Print K corresponds to minimum
    // number of moves
    document.write(K);
}
 
// Driver Code
 
// Given vector
let a = [ 1, 9, 27 ];
 
// Function Call
findMinCostLeteger(a, 3);
 
// This code is contributed by souravghosh0416
 
</script>

5

Complejidad de tiempo: O(N * max(x))
Espacio auxiliar: O(1)