This question is from yesterday’s interviewbit academy entrance test. So the link is unavailable now.
Given an array A of size n.
1 \leq n \leq 10^5
1 \leq A[i] \leq 10^3
find the (\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} A[i] \% A[j]) \% (1e9 + 7)
In other words calculate sum of A[i] \% A[j] for all valid values of i,j and then sum \% (1e9 + 7) .
For Example
Input 1 :
A = [1,2,3]
Output 1 :
5
Explanation 1 :
(1 \% 1) + (1 \% 2) + (1 \% 3)
+ (2 \% 1) + (2 \% 2) + (2 \% 3)
+ (3 \% 1) + (3 \%2) + (3 \% 3)
= 5
Input 2 :
A=[17, 100, 11]
Output 2 :
61
I have applied brute force method. But there might be another way. Kindly give approach.