nik1996's blog

By nik1996, 8 months 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

»
8 months 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 ?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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.

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months 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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Great solution!! Thanks for the help

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I still dont get it. can you give explanation with an example?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Consider a number i so floor of all numbers between i and 2*i(2*i not included) is gonna to to contribute 1 to the sum.And all the numbers between 2*i and 3*i(3*i not included) is gonna to contribute 2 to the sum and so on. The mul var is taking in to account this thing.

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

          I think this solution is wrong because if the array is [1,2,3,4,5] then the output should be 22 but the output of your code is 27.

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

            The correct output is $$$27$$$. Perhaps you are not considering the case where $$$i = j$$$?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Good solution but value of n is too much higher instead you can set value of n in this way and u can see the running time difference 9 sec to 6 sec for all test cases.

    int maxi=INT_MIN;
        int a[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]>maxi)
            maxi=a[i];
        }
        int N = maxi+maxi;
        int h[N] = {0}, sum[N] = {0};
    
»
7 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

You can use another approach. 1. Sort elements. 2. For elements less than sqrt(n) you can run through the array each time(Not forget to remember result of each run, because elements may be repeated). 3. For elements greater than sqrt(n), let's say x, you may use binary search to find the number of elements between xi and x(i+1) (say res), and add res*i to the answer. So overall time complexity will be no less than linearithmic and no greater than O(n*sqrt(n)*log(n)).