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.
1 Like
Spoiler
I think its possible in O(1e6*log(1e6)) using sieve. No need of fancy data structure. Prefix sum should be sufficient.
Similar problem Problem - B - Codeforces .
Its editorial mentions what we need for solving it for n<=1e6 and A[i]<=1e6.
1 Like
Ya thats right … I was thinking a fenwick tree instead of simple prefix sum (I don’t know why 
). I saw this problem and forgot the source. thanks for mentioning it.
1 Like
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
I also try using prefix sum approach but I failed to implement .
Ha vo to hai…Bhai ko kuch bhi puchlo sab Kuch milega😊
1 Like
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;
}
}
```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
yes I’m able to solve that also
Oh great. It would be nice if you share how you did that? By the way, then which one you havent
the 2nd one no of unique quadruple
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
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);
}
}