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

help
23

If someone’s interested, you can even solve the question for constraints like n<=10^6 and A[i]<=10^6. But it might need data structures at disposal.

25

Ya thats right … I was thinking a fenwick tree instead of simple prefix sum (I don’t know why :stuck_out_tongue: ). I saw this problem and forgot the source. thanks for mentioning it.

26

Have you been able to solve the 1st one ? Others were pretty easy. It would be nice if you share your approach for the 1st one

27

I also try using prefix sum approach but I failed to implement .

28

@aryanc403 knows every links.
He is mini Google :stuck_out_tongue:

29

Ha vo to hai…Bhai ko kuch bhi puchlo sab Kuch milega😊

1 Like
30

yes I’m able to solve this…I solve 4/5…just not do 2nd one because I think the question explanation was wrong…
```
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;
    }
    }
```
31

No No, not this one. Even I was able to solve this one. But have you been able to solve that sequence problem where you will be given 4 integers a,b,c,d and the sequemce will be an infinite sequence, you are supposed to find the dth term of the sequence. The sequence will contain natural no.s divisible by atleast a,b or c

32

yes I’m able to solve that also

33

Oh great. It would be nice if you share how you did that? By the way, then which one you havent

34

the 2nd one no of unique quadruple

35

it was simple take a set and put Ax1,Ax2,Ax3,Ax4…AxD
then similarly for B&C…
at last take a counter and output the Dth element in the set

36

from constraint 2 , it can be said some numbers are duplicates, as size of array is 10^5 but elements are 1<=ele <= 10^3
so to avoid same calculations again and again use HashMap or frequency array, count the frequency of each A[i] and A[j], multiply it and taking mod of elements.

ex :
count 1 = 3 (1,1,1)
count 2 = 4 (2,2,2)
so total 3*4 = 12 pairs of (1,2) will be there but we can count all of their’s contribution by muliplying their frequency at once, which will reduce the time complexity.

below is my java solution.

 public class Solution {
public int solve(int[] A) {
    
    int mod = 1000*1000*1000+7;
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i = 0 ; i < A.length ; i++)
        map.put(A[i],map.getOrDefault(A[i],0)+1); 
    

    long sum = 0;
    for(int i = 1 ; i <= 1000; i++){
        for(int j = 1; j <= 1000 ; j++){
            int freA_i = map.getOrDefault(i,0);
            int freA_j = map.getOrDefault(j,0);
            sum +=  (freA_i * freA_j)*(i%j);
            sum = (sum%mod+mod)%mod;
        }
    }
    return (int)(sum%mod);
}

}