Given an array arr[] of size N. The task is to find the sum of arr[i] % arr[j] for all valid pairs. Answer can be large. So, output answer modulo 1000000007
Examples:
Input: arr[] = {1, 2, 3}
Output: 5
(1 % 1) + (1 % 2) + (1 % 3) + (2 % 1) + (2 % 2)
+ (2 % 3) + (3 % 1) + (3 % 2) + (3 % 3) = 5
Input: arr[] = {1, 2, 4, 4, 4}
Output: 10
Approach: Store the frequency of each element and run a nested loop on the frequency array and find the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define mod (int)(1e9 + 7)// Function to return the sum of (a[i] % a[j])// for all valid pairsint Sum_Modulo(int a[], int n){ int max = *max_element(a, a + n); // To store the frequency of each element int cnt[max + 1] = { 0 }; // Store the frequency of each element for (int i = 0; i < n; i++) cnt[a[i]]++; // To store the required answer long long ans = 0; // For all valid pairs for (int i = 1; i <= max; i++) { for (int j = 1; j <= max; j++) { // Update the count ans = ans + cnt[i] * cnt[j] * (i % j); ans = ans % mod; } } return (int)(ans);}// Driver codeint main(){ int a[] = { 1, 2, 3 }; int n = sizeof(a) / sizeof(a[0]); cout << Sum_Modulo(a, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { static int mod = (int)(1e9 + 7);// Function to return the sum of (a[i] % a[j])// for all valid pairsstatic int Sum_Modulo(int a[], int n){ int max = Arrays.stream(a).max().getAsInt(); // To store the frequency of each element int []cnt=new int[max + 1]; // Store the frequency of each element for (int i = 0; i < n; i++) cnt[a[i]]++; // To store the required answer long ans = 0; // For all valid pairs for (int i = 1; i <= max; i++) { for (int j = 1; j <= max; j++) { // Update the count ans = ans + cnt[i] * cnt[j] * (i % j); ans = ans % mod; } } return (int)(ans);}// Driver codepublic static void main(String[] args){ int a[] = { 1, 2, 3 }; int n = a.length; System.out.println(Sum_Modulo(a, n));}}// This code is contributed // by PrinciRaj1992 |
Python3
# Python3 implementation of the approachmod = 10**9 + 7# Function to return the sum of # (a[i] % a[j]) for all valid pairsdef Sum_Modulo(a, n): Max = max(a) # To store the frequency of each element cnt = [0 for i in range(Max + 1)] # Store the frequency of each element for i in a: cnt[i] += 1 # To store the required answer ans = 0 # For all valid pairs for i in range(1, Max + 1): for j in range(1, Max + 1): # Update the count ans = ans + cnt[i] * \ cnt[j] * (i % j) ans = ans % mod return ans# Driver codea = [1, 2, 3]n = len(a)print(Sum_Modulo(a, n))# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Linq;class GFG { static int mod = (int)(1e9 + 7);// Function to return the sum of (a[i] % a[j])// for all valid pairsstatic int Sum_Modulo(int []a, int n){ int max = a.Max(); // To store the frequency of each element int []cnt = new int[max + 1]; // Store the frequency of each element for (int i = 0; i < n; i++) cnt[a[i]]++; // To store the required answer long ans = 0; // For all valid pairs for (int i = 1; i <= max; i++) { for (int j = 1; j <= max; j++) { // Update the count ans = ans + cnt[i] * cnt[j] * (i % j); ans = ans % mod; } } return (int)(ans);}// Driver codepublic static void Main(String[] args){ int []a = { 1, 2, 3 }; int n = a.Length; Console.WriteLine(Sum_Modulo(a, n));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approachlet mod = 1e9 + 7// Function to return the sum of (a[i] % a[j])// for all valid pairsfunction Sum_Modulo(a, n){ let max = a.sort((a, b) => b - a)[0]; // To store the frequency of each element let cnt = new Array(max + 1).fill(0); // Store the frequency of each element for (let i = 0; i < n; i++) cnt[a[i]]++; // To store the required answer let ans = 0; // For all valid pairs for (let i = 1; i <= max; i++) { for (let j = 1; j <= max; j++) { // Update the count ans = ans + cnt[i] * cnt[j] * (i % j); ans = ans % mod; } } return (ans);}// Driver codelet a = [1, 2, 3];let n = a.length;document.write(Sum_Modulo(a, n));// This code is contributed by _saurabh_jaiswal</script> |
Output:
5
Time Complexity: O(MAX2)
Auxiliary Space: O(MAX)
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!
