Número mínimo de operaciones para convertir una secuencia dada en una Progresión Geométrica | conjunto 2

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros, las siguientes tres operaciones se pueden realizar en cualquier elemento de una en una:

  • Agregue uno al elemento.
  • Resta uno del elemento.
  • Deje el elemento sin cambios.

La tarea es encontrar el costo mínimo requerido para convertirlo en una Progresión Geométrica y también encontrar la razón común . 
Nota: Cada operación de suma y resta cuesta 1 unidad.

Ejemplos: 

Entrada: N = 6, arr[] = {1, 11, 4, 27, 15, 33}
Salida: 28 2
Explicación: 
Para r = 1, arr[] = {1, 4, 11, 15, 27, 33 } 
esperado[] = {1, 1, 1, 1, 1, 1} 
costo[] = {0, 3, 10, 14, 26, 32} 
Costo total: ∑ costo = 85

Para r = 2, arr[] = {1, 4, 11, 15, 27, 33} 
esperado[] = {1, 2, 4, 8, 16, 32} 
costo[] = {0, 2, 7, 7, 11, 1}
Costo total: ∑ costo = 28
Para r = 3, arr[] = {1, 4, 11, 15, 27, 33} 
esperado[] = {1, 3, 9, 27, 81, 243} 
costo[] = {0, 1, 2, 12, 54, 210}
Costo total: ∑ costo = 279

Costo mínimo = 28
Razón común = 2

Entrada: N = 7, arr[] = {1, 2, 4, 8, 9, 6, 7}
Salida: 30 1

Enfoque: la idea es iterar sobre el rango de posibles proporciones comunes y verificar las operaciones mínimas requeridas. Siga los pasos a continuación para resolver el problema:

  • Ordenar la array .
  • Encuentre el rango de posibles razones comunes usando la fórmula Ceil( arr[maximum_element] / (N – 1)) .
  • Calcular el número de operaciones requeridas para todas las razones comunes posibles.
  • Encuentre las operaciones mínimas requeridas para cualquiera de las razones comunes.

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

C++

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum cost
void minCost(int arr[], int n)
{
    if (n == 1) {
        cout << 0 << endl;
        return;
    }
 
    // Sort the array
    sort(arr, arr + n);
 
    // Maximum possible common ratios
    float raised = 1 / float(n - 1);
    float temp = pow(arr[n - 1], raised);
    int r = round(temp) + 1;
 
    int i, j, min_cost = INT_MAX;
    int common_ratio = 1;
 
    // Iterate over all possible common ratios
    for (j = 1; j <= r; j++) {
        int curr_cost = 0, prod = 1;
 
        // Calculate operations required
        // for the current common ratio
        for (i = 0; i < n; i++) {
 
            curr_cost += abs(arr[i] - prod);
            prod *= j;
            if (curr_cost >= min_cost)
                break;
        }
 
        // Calculate minimum cost
        if (i == n) {
            min_cost = min(min_cost,
                           curr_cost);
            common_ratio = j;
        }
    }
 
    cout << min_cost << ' ';
    cout << common_ratio << ' ';
}
 
// Driver Code
int main()
{
    // Given N
    int N = 6;
 
    // Given arr[]
    int arr[] = { 1, 11, 4, 27, 15, 33 };
 
    // Function Calling
    minCost(arr, N);
 
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to find minimum cost
static void minCost(int arr[],
                    int n)
{
  if (n == 1)
  {
    System.out.print(0 + "\n");
    return;
  }
 
  // Sort the array
  Arrays.sort(arr);
 
  // Maximum possible common ratios
  float raised = 1 / (float)(n - 1);
  float temp = (float)Math.pow(arr[n - 1],
                               raised);
  int r = (int)(temp) + 1;
 
  int i, j, min_cost = Integer.MAX_VALUE;
  int common_ratio = 1;
 
  // Iterate over all possible
  // common ratios
  for (j = 1; j <= r; j++)
  {
    int curr_cost = 0, prod = 1;
 
    // Calculate operations required
    // for the current common ratio
    for (i = 0; i < n; i++)
    {
      curr_cost += Math.abs(arr[i] -
                            prod);
      prod *= j;
      if (curr_cost >= min_cost)
        break;
    }
 
    // Calculate minimum cost
    if (i == n)
    {
      min_cost = Math.min(min_cost,
                          curr_cost);
      common_ratio = j;
    }
  }
 
  System.out.print(min_cost + " ");
  System.out.print(common_ratio + " ");
}
 
// Driver Code
public static void main(String[] args)
{
  // Given N
  int N = 6;
 
  // Given arr[]
  int arr[] = {1, 11, 4,
               27, 15, 33};
 
  // Function Calling
  minCost(arr, N);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program for above approach
import sys
 
# Function to find minimum cost
def minCost(arr, n):
     
    if (n == 1):
        print(0)
        return
 
    # Sort the array
    arr = sorted(arr)
 
    # Maximum possible common ratios
    raised = 1 / (n - 1)
    temp = pow(arr[n - 1], raised)
    r = round(temp) + 1
 
    min_cost = sys.maxsize
    common_ratio = 1
 
    # Iterate over all possible
    # common ratios
    for j in range(1, r + 1):
        curr_cost = 0
        prod = 1
 
        # Calculate operations required
        # for the current common ratio
        i = 0
        while i < n:
            curr_cost += abs(arr[i] - prod)
            prod *= j
             
            if (curr_cost >= min_cost):
                break
             
            i += 1
 
        # Calculate minimum cost
        if (i == n):
            min_cost = min(min_cost,
                          curr_cost)
            common_ratio = j
 
    print(min_cost, common_ratio)
 
# Driver Code
if __name__ == '__main__':
     
    # Given N
    N = 6
 
    # Given arr[]
    arr = [ 1, 11, 4, 27, 15, 33 ]
 
    # Function calling
    minCost(arr, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for
// the above approach
using System;
 
class GFG{
 
// Function to find minimum cost
static void minCost(int []arr,
                    int n)
{
  if (n == 1)
  {
    Console.Write(0 + "\n");
    return;
  }
 
  // Sort the array
  Array.Sort(arr);
 
  // Maximum possible common ratios
  float raised = 1 / (float)(n - 1);
  float temp = (float)Math.Pow(arr[n - 1],
                               raised);
  int r = (int)(temp) + 1;
 
  int i, j, min_cost = int.MaxValue;
  int common_ratio = 1;
 
  // Iterate over all possible
  // common ratios
  for (j = 1; j <= r; j++)
  {
    int curr_cost = 0, prod = 1;
 
    // Calculate operations required
    // for the current common ratio
    for (i = 0; i < n; i++)
    {
      curr_cost += Math.Abs(arr[i] -
                            prod);
      prod *= j;
       
      if (curr_cost >= min_cost)
        break;
    }
 
    // Calculate minimum cost
    if (i == n)
    {
      min_cost = Math.Min(min_cost,
                          curr_cost);
      common_ratio = j;
    }
  }
 
  Console.Write(min_cost + " ");
  Console.Write(common_ratio + " ");
}
 
// Driver Code
public static void Main(String[] args)
{
   
  // Given N
  int N = 6;
 
  // Given []arr
  int []arr = { 1, 11, 4,
                27, 15, 33 };
 
  // Function Calling
  minCost(arr, N);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// JavaScript program for above approach
 
// Function to find minimum cost
function minCost(arr, n)
{
    if (n == 1) {
        document.write( 0 );
        return;
    }
 
    // Sort the array
    arr.sort((a,b) => a-b);
 
    // Maximum possible common ratios
    var raised = 1 / (n - 1);
    var temp = Math.pow(arr[n - 1], raised);
    var r = Math.round(temp) + 1;
 
    var i, j, min_cost = 1000000000;
    var common_ratio = 1;
 
    // Iterate over all possible common ratios
    for (j = 1; j <= r; j++) {
        var curr_cost = 0, prod = 1;
 
        // Calculate operations required
        // for the current common ratio
        for (i = 0; i < n; i++) {
 
            curr_cost += Math.abs(arr[i] - prod);
            prod *= j;
            if (curr_cost >= min_cost)
                break;
        }
 
        // Calculate minimum cost
        if (i == n) {
            min_cost = Math.min(min_cost,
                           curr_cost);
            common_ratio = j;
        }
    }
 
    document.write( min_cost + ' ');
    document.write( common_ratio + ' ');
}
 
// Driver Code
 
// Given N
var N = 6;
 
// Given arr[]
var arr = [1, 11, 4, 27, 15, 33];
 
// Function Calling
minCost(arr, N);
 
</script>
Producción: 

28 2

 

Complejidad Temporal: O(N * K), donde K es la máxima razón común posible.
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por man_preet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *