Minimizar la suma de la array según la condición dada

Dada una array de enteros A . La tarea es minimizar la suma de los elementos de la array usando la siguiente regla: 
elija dos índices i y j y un número entero arbitrario x , tal que x sea un divisor de A[i] y cámbielos como sigue A[i] = A[i]/x y A[j] = A[j]*x .
Ejemplos: 
 

Entrada: A = { 1, 2, 3, 4, 5 } 
Salida: 14
Divide A[3] entre 2 y luego 
A[3] = 4/2 = 2,
multiplica A[0] por 2 y luego 
A[0] = 1*2 = 2
Array actualizada A = { 2, 2, 3, 2, 5 } 
Por lo tanto suma = 14
Entrada: A = { 2, 4, 2, 3, 7 } 
Salida: 18 
 

Enfoque: si cualquier número se divide por x , entonces es óptimo multiplicar x con el número más pequeño presente en la array.
La idea es obtener el mínimo de la array y encontrar los divisores del elemento en particular y seguir comprobando cuánto se reduce la suma.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum sum
void findMin(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // sort the array to find the
    // minimum element
    sort(arr, arr + n);
 
    int min = arr[0];
    int max = 0;
 
    for (int i = n - 1; i >= 1; i--) {
        int num = arr[i];
        int total = num + min;
        int j;
 
        // finding the number to
        // divide
        for (j = 2; j <= num; j++) {
            if (num % j == 0) {
                int d = j;
                int now = (num / d)
                          + (min * d);
 
                // Checking to what
                // instance the sum
                // has decreased
                int reduce = total - now;
 
                // getting the max
                // difference
                if (reduce > max)
                    max = reduce;
            }
        }
    }
    cout << (sum - max);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findMin(arr, n);
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
     
    // Function to return the minimum sum
    static void findMin(int arr[], int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
     
        // sort the array to find the
        // minimum element
        Arrays.sort(arr);
     
        int min = arr[0];
        int max = 0;
     
        for (int i = n - 1; i >= 1; i--)
        {
            int num = arr[i];
            int total = num + min;
            int j;
     
            // finding the number to
            // divide
            for (j = 2; j <= num; j++)
            {
                if (num % j == 0)
                {
                    int d = j;
                    int now = (num / d) +
                              (min * d);
     
                    // Checking to what
                    // instance the sum
                    // has decreased
                    int reduce = total - now;
     
                    // getting the max
                    // difference
                    if (reduce > max)
                        max = reduce;
                }
            }
        }
        System.out.println(sum - max);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = { 1, 2, 3, 4, 5 };
        int n = arr.length;
        findMin(arr, n);
    }
}
 
// This code is contributed by AnkitRai01

# Function to return the minimum sum
def findMin(arr, n):
    sum = 0
    for i in range(0, n):
        sum = sum + arr[i]
 
    # sort the array to find the
    # minimum element
    arr.sort()
 
    min = arr[0]
    max = 0
 
    for i in range(n - 1, 0, -1):
        num = arr[i]
        total = num + min
 
        # finding the number to
        # divide
        for j in range(2, num + 1):
            if(num % j == 0):
                d = j
                now = (num // d) + (min * d)
 
                # Checking to what
                # instance the sum
                # has decreased
                reduce = total - now
 
                # getting the max
                # difference
                if(reduce > max):
                    max = reduce
 
    print(sum - max)
 
# Driver Code
arr = [1, 2, 3, 4, 5 ]
n = len(arr)
findMin(arr, n)
 
# This code is contributed by Sanjit_Prasad

// C# implementation of the above approach
using System;
     
class GFG
{
     
    // Function to return the minimum sum
    static void findMin(int []arr, int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += arr[i];
     
        // sort the array to find the
        // minimum element
        Array.Sort(arr);
     
        int min = arr[0];
        int max = 0;
     
        for (int i = n - 1; i >= 1; i--)
        {
            int num = arr[i];
            int total = num + min;
            int j;
     
            // finding the number to
            // divide
            for (j = 2; j <= num; j++)
            {
                if (num % j == 0)
                {
                    int d = j;
                    int now = (num / d) +
                              (min * d);
     
                    // Checking to what
                    // instance the sum
                    // has decreased
                    int reduce = total - now;
     
                    // getting the max
                    // difference
                    if (reduce > max)
                        max = reduce;
                }
            }
        }
        Console.WriteLine(sum - max);
    }
     
    // Driver Code
    public static void Main (String[] args)
    {
        int []arr = { 1, 2, 3, 4, 5 };
        int n = arr.Length;
        findMin(arr, n);
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation
 
// Function to return the minimum sum
function findMin(arr, n)
{
    let sum = 0;
    for (let i = 0; i < n; i++)
        sum += arr[i];
 
    // sort the array to find the
    // minimum element
    arr.sort();
 
    let min = arr[0];
    let max = 0;
 
    for (let i = n - 1; i >= 1; i--) {
        let num = arr[i];
        let total = num + min;
        let j;
 
        // finding the number to
        // divide
        for (j = 2; j <= num; j++) {
            if (num % j == 0) {
                let d = j;
                let now = parseInt(num / d)
                          + (min * d);
 
                // Checking to what
                // instance the sum
                // has decreased
                let reduce = total - now;
 
                // getting the max
                // difference
                if (reduce > max)
                    max = reduce;
            }
        }
    }
    document.write(sum - max);
}
 
// Driver Code
    let arr = [ 1, 2, 3, 4, 5 ];
    let n = arr.length;
    findMin(arr, n);
 
</script>

14

Complejidad de tiempo: O ((N * logN) + (N * M)), donde N es el tamaño de la array dada y M es el elemento máximo en la array.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.