I faced this problem in a recent online coding exam for Rakuten. I was unable to optimize it in the given short span of time. Need some help.\n\n\n> You are given an array A of length n. All elements are greater than zero.\nNow, you need to calculate the Sum of Floor(A[i] / A[j]) for all pairs, i.e. for **0 <= i, j < n**\nReturn the answer **modulo 1000003**\n\nSample:\n```\nInput: [3,3,4,4,5]\nOutput: 17\n```\n```\n\nInput: [1,2,3,4,5]\nOutput: 27\n```\n\n**Explanation (Second Sample Case)**\n\nTable denoting the floor division [i.e. floor(A_i / A_j)]\n\n|   | 1  | 2  | 3  | 4  | 5  |\n|---|---|---|---|---|--|\n| 1 | 1 | 0  | 0  | 0 | 0 |\n| 2 | 2 | 1  | 0  | 0 | 0 |\n| 3 | 3 | 1  | 1  | 0 | 0 |\n| 4 | 4 | 2  | 1  | 1  | 0 |\n| 5 | 5 | 2  | 1  |  1 | 1 |\n\n`Sum = 27`\n\nA simple **brute force** method would have a quadratic time complexity. What I am looking for is *linear (O(n))* or atleast *O(n log n)*\n\nAny help would be appreciated, thanks.

I faced this problem in a recent online coding exam for Rakuten. I was unable to optimize it in the given short span of time. Need some help.\n\n\n> You are giv