Suma mínima posible de elementos de array después de realizar la operación dada – Part 1

Dada una array arr[] de enteros positivos y un entero x , la tarea es minimizar la suma de elementos de la array después de realizar la operación dada como máximo una vez. En una sola operación, cualquier elemento del arreglo se puede dividir por x (si es divisible por x) y al mismo tiempo, cualquier otro elemento del arreglo se debe multiplicar por x .
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, 4, 5}, x = 2 
Salida: 14 
Multiplica 1 por x, es decir, 1 * 2 = 2 
Divide 4 por x, es decir, 4/2 = 2 
Y la suma actualizada será 2 + 2 + 3 + 2 + 5 = 14
Entrada: arr[] = {5, 5, 5, 5, 6}, x = 3 
Salida: 26 
 

Enfoque: Para una solución óptima, x debe multiplicarse por el elemento más pequeño de la array y solo el elemento más grande divisible por x debe dividirse por él. Sea sumAfterOperation la suma de los elementos del arreglo calculados después de realizar la operación y sum sea la suma de todos los elementos del arreglo original, entonces la suma minimizada será min(sum, sumAfterOperation) .
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the minimized sum
ll minSum(int arr[], int n, int x)
{
    ll sum = 0;
 
    // To store the largest element
    // from the array which is
    // divisible by x
    int largestDivisible = -1, minimum = arr[0];
    for (int i = 0; i < n; i++) {
 
        // Sum of array elements before
        // performing any operation
        sum += arr[i];
 
        // If current element is divisible by x
        // and it is maximum so far
        if (arr[i] % x == 0 && largestDivisible < arr[i])
            largestDivisible = arr[i];
 
        // Update the minimum element
        if (arr[i] < minimum)
            minimum = arr[i];
    }
 
    // If no element can be reduced then there's no point
    // in performing the operation as we will end up
    // increasing the sum when an element is multiplied by x
    if (largestDivisible == -1)
        return sum;
 
    // Subtract the chosen elements from the sum
    // and then add their updated values
    ll sumAfterOperation = sum - minimum - largestDivisible
                           + (x * minimum) + (largestDivisible / x);
 
    // Return the minimized sum
    return min(sum, sumAfterOperation);
}
 
// Driver code
int main()
{
    int arr[] = { 5, 5, 5, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    cout << minSum(arr, n, x);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the minimized sum
static int minSum(int arr[], int n, int x)
{
    int sum = 0;
 
    // To store the largest element
    // from the array which is
    // divisible by x
    int largestDivisible = -1,
        minimum = arr[0];
    for (int i = 0; i < n; i++)
    {
 
        // Sum of array elements before
        // performing any operation
        sum += arr[i];
 
        // If current element is divisible
        // by x and it is maximum so far
        if (arr[i] % x == 0 &&
            largestDivisible < arr[i])
            largestDivisible = arr[i];
 
        // Update the minimum element
        if (arr[i] < minimum)
            minimum = arr[i];
    }
 
    // If no element can be reduced then
    // there's no point in performing the
    // operation as we will end up increasing
    // the sum when an element is multiplied by x
    if (largestDivisible == -1)
        return sum;
 
    // Subtract the chosen elements from the
    // sum and then add their updated values
    int sumAfterOperation = sum - minimum - largestDivisible +
                            (x * minimum) + (largestDivisible / x);
 
    // Return the minimized sum
    return Math.min(sum, sumAfterOperation);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 5, 5, 5, 5, 6 };
    int n =arr.length;
    int x = 3;
    System.out.println(minSum(arr, n, x));
}
}
 
// This code is contributed
// by Code_Mech

# Python3 implementation of the approach
 
# Function to return the minimized sum
def minSum(arr, n, x):
 
    Sum = 0
 
    # To store the largest element
    # from the array which is
    # divisible by x
    largestDivisible, minimum = -1, arr[0]
    for i in range(0, n):
 
        # Sum of array elements before
        # performing any operation
        Sum += arr[i]
 
        # If current element is divisible by x
        # and it is maximum so far
        if(arr[i] % x == 0 and
           largestDivisible < arr[i]):
            largestDivisible = arr[i]
 
        # Update the minimum element
        if arr[i] < minimum:
            minimum = arr[i]
 
    # If no element can be reduced then there's
    # no point in performing the operation as
    # we will end up increasing the sum when an
    # element is multiplied by x
    if largestDivisible == -1:
        return Sum
 
    # Subtract the chosen elements from the
    # sum and then add their updated values
    sumAfterOperation = (Sum - minimum - largestDivisible +
                        (x * minimum) + (largestDivisible // x))
 
    # Return the minimized sum
    return min(Sum, sumAfterOperation)
 
# Driver code
if __name__ == "__main__":
 
    arr = [5, 5, 5, 5, 6]
    n = len(arr)
    x = 3
    print(minSum(arr, n, x))
 
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the minimized sum
static int minSum(int[] arr, int n, int x)
{
    int sum = 0;
 
    // To store the largest element
    // from the array which is
    // divisible by x
    int largestDivisible = -1,
        minimum = arr[0];
    for (int i = 0; i < n; i++)
    {
 
        // Sum of array elements before
        // performing any operation
        sum += arr[i];
 
        // If current element is divisible
        // by x and it is maximum so far
        if (arr[i] % x == 0 &&
            largestDivisible < arr[i])
            largestDivisible = arr[i];
 
        // Update the minimum element
        if (arr[i] < minimum)
            minimum = arr[i];
    }
 
    // If no element can be reduced then
    // there's no point in performing the
    // operation as we will end up increasing
    // the sum when an element is multiplied by x
    if (largestDivisible == -1)
        return sum;
 
    // Subtract the chosen elements from the
    // sum and then add their updated values
    int sumAfterOperation = sum - minimum - largestDivisible +
                            (x * minimum) + (largestDivisible / x);
 
    // Return the minimized sum
    return Math.Min(sum, sumAfterOperation);
}
 
// Driver code
public static void Main()
{
    int[] arr = { 5, 5, 5, 5, 6 };
    int n = arr.Length;
    int x = 3;
    Console.WriteLine(minSum(arr, n, x));
}
}
 
// This code is contributed
// by Code_Mech

<?php
// PHP implementation of the approach
 
// Function to return the minimized sum
function minSum($arr, $n, $x)
{
    $sum = 0;
 
    // To store the largest element
    // from the array which is
    // divisible by x
    $largestDivisible = -1;
    $minimum = $arr[0];
    for ($i = 0; $i < $n; $i++)
    {
 
        // Sum of array elements before
        // performing any operation
        $sum += $arr[$i];
 
        // If current element is divisible
        // by x and it is maximum so far
        if ($arr[$i] % $x == 0 &&
            $largestDivisible < $arr[$i])
            $largestDivisible = $arr[$i];
 
        // Update the minimum element
        if ($arr[$i] < $minimum)
            $minimum = $arr[$i];
    }
 
    // If no element can be reduced then
    // there's no point in performing the
    // operation as we will end up increasing
    // the sum when an element is multiplied by x
    if ($largestDivisible == -1)
        return $sum;
 
    // Subtract the chosen elements from the
    // sum and then add their updated values
    $sumAfterOperation = $sum - $minimum - $largestDivisible +
                        ($x * $minimum) + ($largestDivisible / $x);
 
    // Return the minimized sum
    return min($sum, $sumAfterOperation);
}
 
// Driver code
$arr = array( 5, 5, 5, 5, 6 );
$n = sizeof($arr);
$x = 3;
 
print(minSum($arr, $n, $x));
 
// This code is contributed by Ryuga
?>

<script>
// javascript implementation of the approach   
// Function to return the minimized sum
    function minSum(arr , n , x) {
        var sum = 0;
 
        // To store the largest element
        // from the array which is
        // divisible by x
        var largestDivisible = -1, minimum = arr[0];
        for (i = 0; i < n; i++) {
 
            // Sum of array elements before
            // performing any operation
            sum += arr[i];
 
            // If current element is divisible
            // by x and it is maximum so far
            if (arr[i] % x == 0 && largestDivisible < arr[i])
                largestDivisible = arr[i];
 
            // Update the minimum element
            if (arr[i] < minimum)
                minimum = arr[i];
        }
 
        // If no element can be reduced then
        // there's no point in performing the
        // operation as we will end up increasing
        // the sum when an element is multiplied by x
        if (largestDivisible == -1)
            return sum;
 
        // Subtract the chosen elements from the
        // sum and then add their updated values
        var sumAfterOperation = sum - minimum - largestDivisible
        + (x * minimum) + (largestDivisible / x);
 
        // Return the minimized sum
        return Math.min(sum, sumAfterOperation);
    }
 
    // Driver code
     
        var arr = [ 5, 5, 5, 5, 6 ];
        var n = arr.length;
        var x = 3;
        document.write(minSum(arr, n, x));
 
// This code contributed by aashish1995
</script>

26

Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo 
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.