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:
- Calcule el LCM de todos los elementos de la array .
- 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.
- 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.
- 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++
// 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
// 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
# 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#
// 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
Javascript
<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>
Producción:
10
Complejidad temporal: O(N)
Espacio auxiliar: O(1)