nik1996's blog

By nik1996, 5 weeks ago, In English,

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?

Thanks in advance.

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Is there any constraint on the values that the elements of the array may have ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay, the size of array n is 1<=n<=1e5 and each element arr[i] is 1<=arr[i]<=1e5.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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   Vote: I like it +9 Vote: I do not like it
        Code with a little comment

        Note: I assume there are no same elements in the array. Otherwise, the code can easily be modified.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You're using suffix sums. I think use of prefix sums would have been more intuitive. But anyways, good logic.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Great solution!! Thanks for the help