Sum of A[i] % A[j] for all valid i,j

#1

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.

1 Like
#2

The problem is pretty easy.

sum = A[1] + A[2] + … A[N]
ans = sum * sum

You can solve it by firstly taking sum of all elements and then multiplying sum by itself, as i will give:

ans = (A[1] + A[2] + … A[N]) * (A[1] + A[2] + … A[N])
ans = A[1] * (A[1] + A[2] + … A[N]) + A[2] * (A[1] + A[2] + … A[N]) … + A[N] * (A[1] + A[2] + … A[N])
which will generate all possible combinations.

Note: Keep in mind to take mod at all steps as well.

#3

There is another simple way to do it .
If you observer closely the range of A[i] is 10^3 .

so you can make all the combinations of values of A[i] in O(n^2) in a map lets say mp.
now make frequency array of given n elements .

and for every combination of mp i.e. (mp[i],mp[j]) and multiply this value with freq[mp[i]] . and at least give answer with mod.

2 Likes
#4

why are you multiplying ? shouldn’t u take mod of A[i],A[j] as mentioned in the question?

#5

I am storing i%j for all 10^3 elements in map . so it will be a 10^6 size map having all possible A[i]%A[j] results .

loop will not be on n elements , it will on unique elements present in array .
I am multiplying because if you see repeating elements they will occur again and again write for case 1 3 4 4 4 you will see you will need to multiply with their frequency and then take mod at last .

2 Likes
#6

ok got it now…

#7

i still did not get why are we multiplying.
Does it hold true for this test case Input : 1 , 2, 3
Output : 5

#8

Can u explain this by taking an example…

#9

I don’t think this is working or may be I might getting it wrong. For simple test case as Input 1 the actual output is 5 while with your approach it is giving 36.

#11

Sorry I didn’t get it. Can you explain it with an example.

#12

well okay …
take 1 2 4 and 1 2 4 4 4 as test cases

for test case : 1 2 4
1%1 + 2%1 + 4%1
1%2 + 2%2 + 4%2
1%4 + 2%4 + 4%4

for test case 1 2 4 4 4

1%1 + 2%1 + 4%1 + 4%1 + 4%1
1%2 + 2%2 + 4%2 + 4%2 + 4%2
1%4 + 2%4 + 4%4 + 4%4 + 4%4
1%4 + 2%4 + 4%4 + 4%4 + 4%4
1%4 + 2%4 + 4%4 + 4%4 + 4%4

so if you can see 4 was 3 times in this test case so 4%4 are 3*3 = 9 times in this test case.
same for 2%4 which is 3 times now , same goes for all … 4%1 , 4%2 , 1%4 … all 3 times .
and see those (A[i],A[j]) are not repeating like 1%2 they are same as before .
I hope you will get it now . sorry if I explained badly in previous comment .

1 Like
#14

Wont work. assume the sample test case 1 2 3 . Your approach will give 36 answer.

#15

After looking the constraints this question can be solve down easily.It is given that A[i] value max will be 10^3 and the n will be max upto 10^5 which means in worst case there will be duplicacy arises.So just make an array ,vector,set or map up to you to choose and store distinct elements in it. Also store side by side every element frequency which was there in intial array.Now you just solved this question in o(n^2) because max elements you have in your new array will be 10^3 total and you solve in o(n^2).
Lets solve with an example

example - 2 2 3 3 3 4
frequency array look like - fre[2]=2 , fre[3] = 3, fre[4]=1;
new array - 2 3 4
now just use two loops and just mutiply it with its frequencies.
(2%3)*fre[2]*fre[3]+(2%4)*fre[2]*fre[4]+(3%2)*fre[3]*fre[2] +(3%4)*fre[3]*fre[4]+(4%2)*fre[4]*fre[2]+(4%3)*fre[4]*fre[3];

And dont forget to mod …

#16

But if suppose the array contain only unique element then the worst case complexity is O(n^2).
Can we do also in O(n) complexity @karangreat234 @andrew1234 can u plz help me bro😊

#17

If there is only unique elements then I do not find any approach for an array of size 10^5 in 1 sec time limit . But as mentioned if the value of a[i] is less than 10^3 we can do it by storing frequencies of each element.

#18

I think this is an interview bit 1st question of entrance exam in interview bit academy…

it is just simple the constraints are so small so you can easily take an aray of size 10^3 and count the numbers…

finally take 2 loops if 1000

for(int i = 0; i < A.size(); i++)
   cnt[A[i]]++;

    for(int i = 1; i <= 1000; i++){
       for(int j = 1; j <= 1000; j++){
          ans = ans + cnt[i]*cnt[j]*(i%j);
          ans = ans%mod;
    }
    }
1 Like
#19

since the time complexity of this solution is constant i.e 10^6…
which is enough to get AC

#20

BTW how many questions you did out of 5??

#21

the whole array do not able to be unique since the value of a[i] ranges to 1000 only…
so at worst time it will be 10^6 only…

1 Like
#22

Yaa… Thanks bro @andrew1234 got it…