### nik1996's blog

By nik1996, 5 weeks ago, ,

Hello all, Recently I was attempting the following problem: Given an array of integers, arr. Find sum of floor of (arr[i]/arr[j]) for all pairs of indices (i,j).

e.g. arr[]={1,2,3,4,5}, Sum=27.

I could only think of naive O(n^2) solution. Is there any other better approach?

•
• +10
•

 » 5 weeks ago, # |   +5 Is there any constraint on the values that the elements of the array may have ?
•  » » 5 weeks ago, # ^ |   0 Okay, the size of array n is 1<=n<=1e5 and each element arr[i] is 1<=arr[i]<=1e5.
•  » » » 5 weeks ago, # ^ |   +3 Firstly, precalculate b[i] values which is equal to count of numbers  ≥ i, it can be done in O(MX). Then for each number, go like a sieve and now calculating how answer change is easy since we know the count of elements between this and next multiple.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   +9 Code with a little commentconst int MX = 100005; int cnt[MX], b[MX]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base :: sync_with_stdio(0); cin.tie(0), cout.tie(0); int n, x; cin >> n; for (int i = 1; i <= n; i++) { cin >> x; cnt[x]++; } for (int i = MX - 1; i >= 1; i--) { b[i] = b[i + 1] + cnt[i]; } long long res = 0; for (int i = 1; i < MX; i++) { if (cnt[i] == 0) { continue; } for (int j = i, mul = 1; j < MX; j += i, mul++) { /// there are b[j] - b[j + i] elements which adds mul to the ans res += 1LL * (b[j] - b[min(MX - 1, j + i)]) * mul * cnt[i]; /// *cnt[i] because we have cnt[i] times i } } cout << res << endl; return 0; } Note: I assume there are no same elements in the array. Otherwise, the code can easily be modified.
•  » » » » » 5 weeks ago, # ^ |   0 You're using suffix sums. I think use of prefix sums would have been more intuitive. But anyways, good logic.
•  » » » » » 5 weeks ago, # ^ |   0 Great solution!! Thanks for the help