Sum Calculation

For a given array, find sum of floor(arr[i]/arr[j]) for all pairs (i,j).
Ex: {1,2,3,4,5} = 27
Can someone please suggest any approach better than O(N^2)?

3 Likes

Asked in oppo R&D interview in DTU right

1 Like

https://codeforces.com/blog/entry/65363?mobile=false

1 Like

Thanks for the link, Prefix sum + sieve worked fine for this problem. :slight_smile:

1 Like

Hackerearth Internship and Delhivery backend developer online test.

2 Likes