Maximiza la suma del módulo con cada elemento de Array

Dada una array A[] que consta de N enteros positivos, la tarea es encontrar el valor máximo posible de: 
 

F(M) = M % A[0] + M % A[1] + …. + M % A[N -1] donde M puede ser cualquier valor entero

Ejemplos: 
 

Entrada: arr[] = {3, 4, 6} 
Salida: 10 
Explicación: 
La suma máxima ocurre para M = 11. 
(11 % 3) + (11 % 4) + (11 % 6) = 2 + 3 + 5 = 10
Entrada: arr[] = {2, 5, 3} 
Salida: 7 
Explicación: 
La suma máxima ocurre para M = 29. 
(29 % 2) + (29 % 5) + (29 % 3) = 1 + 4 + 2 = 7. 
 

Enfoque: 
siga los pasos a continuación para resolver el problema: 
 

1. Calcule el LCM de todos los elementos de la array .
2. Si M es igual al MCM de la array, entonces F(M) = 0, es decir, el valor mínimo posible de F(M) . Esto se debe a que M % a[i] siempre será 0 para cada i- ^ésimo índice.
3. Para M = LCM de los elementos de la array – 1, F(M) se maximiza. Esto se debe a que M % a[i] es igual a a[i] – 1 para cada i ^-ésimo índice, que es el máximo posible.
4. Por lo tanto, el valor máximo posible de F(M) puede ser Suma de elementos de array – N.

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

// C++ program to find the
// maximum sum of modulus
// with every array element
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// maximum sum of modulus
// with every array element
int maxModulosum(int a[], int n)
{
    int sum = 0;
 
    // Sum of array elements
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
 
    // Return the answer
    return sum - n;
}
 
// Driver Program
int main()
{
    int a[] = { 3, 4, 6 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << maxModulosum(a, n);
 
    return 0;
}

// Java program to find the maximum
// sum of modulus with every array
// element
import java.io.*;
 
class GFG{
 
// Function to return the maximum
// sum of modulus with every array
// element
static int maxModulosum(int a[], int n)
{
    int sum = 0;
     
    // Sum of array elements
    for(int i = 0; i < n; i++)
    {
       sum += a[i];
    }
     
    // Return the answer
    return sum - n;
}
     
// Driver Code
public static void main (String[] args)
{
    int a[] = new int[]{ 3, 4, 6 };
    int n = a.length;
     
    System.out.println(maxModulosum(a, n));
}
}
 
// This code is contributed by Shubham Prakash

# Python3 program to find the
# maximum sum of modulus
# with every array element
 
# Function to return the
# maximum sum of modulus
# with every array element
def maxModulosum(a, n):
 
    sum1 = 0;
 
    # Sum of array elements
    for i in range(0, n):
        sum1 += a[i];
     
    # Return the answer
    return sum1 - n;
 
# Driver Code
a = [ 3, 4, 6 ];
n = len(a);
print(maxModulosum(a, n));
 
# This code is contributed by Code_Mech

// C# program to find the maximum
// sum of modulus with every array
// element
using System;
class GFG{
 
// Function to return the maximum
// sum of modulus with every array
// element
static int maxModulosum(int []a, int n)
{
    int sum = 0;
     
    // Sum of array elements
    for(int i = 0; i < n; i++)
    {
        sum += a[i];
    }
     
    // Return the answer
    return sum - n;
}
     
// Driver Code
public static void Main(String[] args)
{
    int []a = new int[]{ 3, 4, 6 };
    int n = a.Length;
     
    Console.Write(maxModulosum(a, n));
}
}
 
// This code is contributed
// by shivanisinghss2110

<script>
 
    // Javascript program to find the
    // maximum sum of modulus
    // with every array element
     
    // Function to return the
    // maximum sum of modulus
    // with every array element
    function maxModulosum(a, n)
    {
        let sum = 0;
 
        // Sum of array elements
        for (let i = 0; i < n; i++) {
            sum += a[i];
        }
 
        // Return the answer
        return sum - n;
    }
      
    let a = [ 3, 4, 6 ];
    let n = a.length;
    document.write(maxModulosum(a, n));
 
</script>

10

Complejidad temporal: O(N)  
Espacio auxiliar: O(1)