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> |
Output:
10
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
