CODEWITHSUNDEEP
algorithmoptimizationtime-complexity
Debu Shinobi
Debu Shinobi

Reputation: 2582

Could anyone tell me a better solution for this problem? I could only think of brute force way which is O(n^2)

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. 

Input: arr[]={1,2,3,4,5} 
Output: Sum=27.

Explanation:

(1/1)+(1/5)+(1/4)+(1/2)+(1/3) = 1+0+0+0+0 = 1

(5/1)+(5/5)+(5/4)+(5/2)+(5/3) = 5+1+1+2+1 = 10

(4/1)+(4/5)+(4/4)+(4/2)+(4/3) = 4+0+1+2+1 = 8

(2/1)+(2/5)+(2/4)+(2/2)+(2/3) = 2+0+0+1+0 = 3

(3/1)+(3/5)+(3/4)+(3/2)+(3/3) = 3+0+0+1+1 = 5

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

Thanks in advance.

Upvotes: 3

Views: 2263

Answers (2)

user1196549
user1196549

Reputation:

A possibility resides in "quickly" skipping the elements that are the same integer multiple of a given element (after rounding).

For the given example, the vertical bars below delimit runs of equal ratios (the lower triangle is all zeroes and ignored; I show the elements on the left and the ratios on the right):

1 -> 2 | 3 | 4 | 5 ≡ 2 | 3 | 4 | 5
2 ->     3 | 4   5 ≡     1 | 2   2
3 ->         4   5 ≡         1   1
4 ->             5 ≡             1

For bigger arrays, the constant runs can be longer.

So the algorithm principle is

  • sort all elements increasingly;

  • process the elements from smallest to largest;

    • for a given element, find the index of the first double and count the number of skipped elements;
    • from there, find the index of the first triple and count twice the number of skipped elements;
    • continue with higher multiples until you exhaust the tail of the array.

A critical operation is to "find the next multiple". This should be done by an exponential search followed by a dichotomic search, so that the number of operations remains logarithmic in the number of elements to skip (a pure dichotomic search would be logarithmic in the total number of remaining elements). Hence the cost of a search will be proportional to the sum of the logarithms of the distances between the multiples.

Hopefully, this sum will be smaller than the sum of the distances themselves, though in the worst case the complexity remains O(N). In the best case, O(log(N)).

A global analysis is difficult and in theory the worst-case complexity remains O(N²); but in practice it could go down to O(N log N), because the worst case would require that the elements grow faster than a geometric progression of common ratio 2.

Addendum:

If the array contains numerous repeated values, it can be beneficial to compress it by storing a repetition count and a single instance of every value. This can be done after sorting.

Upvotes: 2

Adam Lopes
Adam Lopes

Reputation: 74

int[] arr = { 1, 2, 3, 4, 5 };

int result = 0;
int BuffSize = arr.Max() * 2;
int[] b = new int[BuffSize + 1];
int[] count = new int[BuffSize];

for (int i = 0; i < arr.Length; ++i)
    count[arr[i]]++;

for (int i = BuffSize - 1; i >= 1; i--)
{
    b[i] = b[i + 1] + count[i];
}

for (int i = 1; i < BuffSize; i++)
{
    if (count[i] == 0)
    {
        continue;
    }
    for (int j = i, mul = 1; j < BuffSize; j += i, mul++)
    {
        result += 1 * (b[j] - b[Math.Min(BuffSize - 1, j + i)]) * mul * count[i];
    }
}

This code takes advantage of knowing difference between each successive value ahead of time, and only process the remaining portion of the array rather than redundantly processing the entire thing n^2 times, I believe it has a worst case runtime of O(n*sqrt(n)*log(n))

Upvotes: 0

Related Questions