Given an array arr[] consisting of N positive integers, the task is to find the maximum value of ∑(M mod arr[i]), where arr[i] is any array element, for a non-negative integer M.
Examples:
Input: arr[] = {3, 4, 6}
Output: 10
Explanation: For M = 11, (11 mod 3) + (11 mod 4) + (11 mod 6) =10Input: arr[]={7, 46, 11, 20, 11}
Output: 90
Approach: Follow the steps below to solve the problem:
- Since A mod B is the remainder when A divided by B, then the maximum value of the expression ∑(M mod arr[i]) is:
(M mod Arr[0]) + (M mod Arr[1]) +. . . + (M mod Arr[N-1]) = (Arr[0] − 1) + (Arr[1] − 1) + · · · + (Arr[N-1]− 1)
- Considering K = Arr[0] × Arr[1] × ···· × Arr[n – 1], then (K mod Arr[i]) = 0 for each i in range [0, N – 1]
- Therefore, ((K − 1) mod Arr[i]) = Arr[i] − 1. Therefore, for M = K – 1, the optimal result can be obtained.
Below is the implementation of the above approach :
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate maximum modulo// sum possible from a given arrayint MaximumModuloSum(int Arr[], int N){ // Stores the sum int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { sum += Arr[i] - 1; } return sum;}// Driver Codeint main(){ int arr[] = { 3, 4, 6 }; int N = sizeof(arr) / sizeof(arr[0]); cout << MaximumModuloSum(arr, N); return 0;} |
Java
// Java Program to implement// the above approachimport java.io.*;class GFG { public static int MaximumModuloSum(int Arr[], int N) { // Stores the sum int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { sum += Arr[i] - 1; } return sum; } public static void main(String[] args) { int arr[] = { 3, 4, 6 }; int N = 3; System.out.println(MaximumModuloSum(arr, N)); }}// This code is contributed by aditya7409. |
Python3
# Python 3 Program to implement# the above approach# Function to calculate maximum modulo# sum possible from a given arraydef MaximumModuloSum( Arr, N): # Stores the sum sum = 0; # Traverse the array for i in range( N ): sum += Arr[i] - 1; return sum;# Driver Codeif __name__ == "__main__": arr = [ 3, 4, 6 ]; N = len(arr) print(MaximumModuloSum(arr, N)) # This code is contributed by chitranayal. |
C#
// C# program for the above approach using System;class GFG { public static int MaximumModuloSum(int[] Arr, int N) { // Stores the sum int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { sum += Arr[i] - 1; } return sum; } // Driver code static void Main() { int[] arr = { 3, 4, 6 }; int N = 3; Console.WriteLine(MaximumModuloSum(arr, N)); }}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// Javascript Program to implement// the above approach// Function to calculate maximum modulo// sum possible from a given array function MaximumModuloSum(Arr, N) { // Stores the sum var sum = 0; // Traverse the array for (i = 0; i < N; i++) { sum += Arr[i] - 1; } return sum; } // Driver code var arr = [ 3, 4, 6 ]; var N = 3; document.write(MaximumModuloSum(arr, N));// This code is contributed by umadevi9616</script> |
10
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
