Maximice la suma de arrays eligiendo pares y dividiendo una parte y multiplicando la otra por K

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N y entero K , la tarea es maximizar la suma de la array realizando las siguientes operaciones cualquier número de veces (posiblemente cero):

  • Elija dos índices, i y j donde arr[i] debe ser un múltiplo de K .
  • Hacer arr[i] = arr[i]/K y arr[j] = K*arr[j]
  • Después de realizar las operaciones anteriores, la suma de los elementos del arreglo debe ser máxima.

Ejemplos:

Entrada: arr[] = {6, 6, 3}, N = 3, K = 3
Salida: 57
Explicación:  La secuencia óptima para la cual se maximizaría la suma de los elementos de la array es:

  • Tome i = 0 y j = 1 , arr[0] = arr[0]/3 = 2, arr[1] = arr[1]*3 = 18, ahora la nueva array se convierte en [2, 18, 3]
  • Tome i = 2 y j = 1 , arr[2] = arr[2]/3 = 1, arr[1] = arr[1]*3 = 54, la array se convierte en [2, 54, 1]

Suma = 2 + 54 + 1 = 57

Entrada: arr[] = {1, 2, 3, 4, 5}, N = 5, K = 2
Salida: 46
Explicación : La operación realizada es:
Tomar i = 1 y j = 4 , arr[1] = arr [1]/2 = 1, arr[4] = arr[4]*2 = 10. Ahora arr[] = {1, 1, 3, 4, 10}. 
Toma i = 3 y j = 4 , arr[3] = arr[3]/2 = 2, arr[4] = arr[4]*2 = 20. Ahora arr[] = {1, 1, 3, 2 , 20}.
Toma i = 3 y j = 4 , arr[3] = arr[3]/2 = 1, arr[4] = arr[4]*2 = 40. Ahora arr[] = {1, 1, 3, 1 , 40}
Suma = 1 + 1+ 3 + 1 + 40 = 46.

 

Enfoque: el enfoque codicioso es dividir todos los elementos de la array que son múltiplos de K por K y contar el número total de operaciones de división (por ejemplo, X ) realizadas. Luego ordene la array y multiplique el elemento máximo de la array X veces por K , es decir , arr[N-1] = arr[N-1]*K X . Siga los pasos a continuación para resolver este problema:

  • Cree una variable total_division = 0 para almacenar el número total de divisiones realizadas.
  • Iterar sobre el rango [0, N) usando el índice variable y realizar las siguientes tareas:
    • Si arr[index] %K = 0 , averigüe cuántas veces se puede dividir arr[index] por K e incremente total_division esa cantidad de veces .
  • Ordene la array arr[] .
  • Ejecute un ciclo while hasta que total_division > 0 y haga arr[N-1] = arr[N-1] * K y disminuya total_division.
  • Cree una variable maximo_sum = 0.
  • Iterar sobre el rango [0, N) usando el índice variable y realizar las siguientes tareas:
    • Actualice la suma_máxima += arr[índice] .
  • Después de realizar los pasos anteriores, imprima el valor de maximum_sum como respuesta.

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;
 
// Utility function
int MaximumSumOperations(int arr[], int N,
                         int K)
{
    if (N == 1) {
        return arr[0];
    }
 
    // Variable to count total operations
    int total_division = 0;
 
    // Perform the division operation on
    // the elements multiple of K
    for (int index = 0; index < N;
         index++) {
        if (arr[index] % K == 0) {
            while (arr[index] > 1
                   && arr[index] % K == 0) {
                arr[index] = arr[index] / K;
                total_division++;
            }
        }
    }
 
    sort(arr, arr + N);
 
    // Update maximum element and
    // decrement total_division
    while (total_division > 0) {
        arr[N - 1] = K * arr[N - 1];
        total_division--;
    }
 
    int maximum_sum = 0;
    for (int index = 0; index < N;
         index++) {
        maximum_sum += arr[index];
    }
 
    // Return maximum_sum
    return maximum_sum;
}
 
// Driver Code
int main()
{
    int arr[5] = { 1, 2, 3, 4, 5 };
    int N = 5, K = 2;
 
    // Function called
    cout << MaximumSumOperations(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
public class GFG
{
 
  // Utility function
  static int MaximumSumOperations(int arr[], int N,
                                  int K)
  {
    if (N == 1) {
      return arr[0];
    }
 
    // Variable to count total operations
    int total_division = 0;
 
    // Perform the division operation on
    // the elements multiple of K
    for (int index = 0; index < N;
         index++) {
      if (arr[index] % K == 0) {
        while (arr[index] > 1
               && arr[index] % K == 0) {
          arr[index] = arr[index] / K;
          total_division++;
        }
      }
    }
 
    Arrays.sort(arr);
 
    // Update maximum element and
    // decrement total_division
    while (total_division > 0) {
      arr[N - 1] = K * arr[N - 1];
      total_division--;
    }
 
    int maximum_sum = 0;
    for (int index = 0; index < N;
         index++) {
      maximum_sum += arr[index];
    }
 
    // Return maximum_sum
    return maximum_sum;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = 5, K = 2;
 
    // Function called
    System.out.println(MaximumSumOperations(arr, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python code for the above approach
 
# Utility function
def MaximumSumOperations(arr, N, K):
    if (N == 1):
        return arr[0];
 
    # Variable to count total operations
    total_division = 0;
 
    # Perform the division operation on
    # the elements multiple of K
    for index in range(N):
        if (arr[index] % K == 0):
            while (arr[index] > 1 and arr[index] % K == 0):
                arr[index] = arr[index] // K;
                total_division += 1
 
    arr.sort()
 
    # Update maximum element and
    # decrement total_division
    while (total_division > 0):
        arr[N - 1] = K * arr[N - 1];
        total_division -= 1
 
    maximum_sum = 0;
    for index in range(N):
        maximum_sum += arr[index];
 
    # Return maximum_sum
    return maximum_sum;
 
# Driver Code
arr = [1, 2, 3, 4, 5]
N = 5
K = 2
 
# Function called
print(MaximumSumOperations(arr, N, K));
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
class GFG
{
   
  // Utility function
  static int MaximumSumOperations(int []arr, int N,
                                  int K)
  {
    if (N == 1) {
      return arr[0];
    }
 
    // Variable to count total operations
    int total_division = 0;
 
    // Perform the division operation on
    // the elements multiple of K
    for (int index = 0; index < N;
         index++) {
      if (arr[index] % K == 0) {
        while (arr[index] > 1
               && arr[index] % K == 0) {
          arr[index] = arr[index] / K;
          total_division++;
        }
      }
    }
 
    Array.Sort(arr);
 
    // Update maximum element and
    // decrement total_division
    while (total_division > 0) {
      arr[N - 1] = K * arr[N - 1];
      total_division--;
    }
 
    int maximum_sum = 0;
    for (int index = 0; index < N;
         index++) {
      maximum_sum += arr[index];
    }
 
    // Return maximum_sum
    return maximum_sum;
  }
 
  // Driver code
  public static void Main()
  {
    int []arr = { 1, 2, 3, 4, 5 };
    int N = 5, K = 2;
 
    // Function called
    Console.Write(MaximumSumOperations(arr, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach
 
       // Utility function
       function MaximumSumOperations(arr, N, K)
       {
           if (N == 1)
           {
               return arr[0];
           }
 
           // Variable to count total operations
           let total_division = 0;
 
           // Perform the division operation on
           // the elements multiple of K
           for (let index = 0; index < N;
               index++) {
               if (arr[index] % K == 0) {
                   while (arr[index] > 1
                       && arr[index] % K == 0) {
                       arr[index] = Math.floor(arr[index] / K);
                       total_division++;
                   }
               }
           }
 
           arr.sort(function (a, b) { return a - b })
 
           // Update maximum element and
           // decrement total_division
           while (total_division > 0) {
               arr[N - 1] = K * arr[N - 1];
               total_division--;
           }
 
           let maximum_sum = 0;
           for (let index = 0; index < N;
               index++) {
               maximum_sum += arr[index];
           }
 
           // Return maximum_sum
           return maximum_sum;
       }
 
       // Driver Code
       let arr = [1, 2, 3, 4, 5];
       let N = 5, K = 2;
 
       // Function called
       document.write(MaximumSumOperations(arr, N, K));
 
        // This code is contributed by Potta Lokesh
   </script>
Producción

46

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

Publicación traducida automáticamente

Artículo escrito por geekyss 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 *