CareerCup

This is impossible to do in O(n). Minimum is O(n^2).

Proof:

Let A be {1, 2, 4, 8, ... 2^n}

We must compute all different |A_i - A_j|. We will show that we have 1 + n(n-1)/2 such differences. First of all, because of the modulo, we can only consider |A_j - A_i| with j > i. We also have a difference of 0, from |A_i - A_i| (this is where the 1+ comes from in the formula above).

Assume that we have i1 and j1 with i1<j1 and i2 and j2 with i2<i2, for which |A_i1 - A_j1| == |A_i2 - A_j2|. We will prove that i1 == i2 and j1 == j2. Because of the ordering between i* and j*, we have A_j1 - A_i1 = A_j2 - A_i2. This is equivalent to 2^j2 - 2^i2 == 2^j1 - 2^i1, turns to 2^i2(2^(j2-i2) + 1) == 2^i1(2^(j1-i1) + 1). From this, 2^i2 has to divide 2^i1, since the parenthesis on the right (2^(j1-i1) + 1) is odd and cannot be divided by 2. In turn, 2^i1 has to divide 2^i2. Therefore i2 == i1 == i. From this, 2^(j1-i) + 1 == 2^(j2-i) + 1, which gives 2^(j1-i) == 2^(j2-i), which gives j1 == j2 == j. QED

This proves that among all pairs (i, j) with i < j, each has a unique difference |A_j - A_i|. They are n(n-1) / 2 pairs, which will take O(n^2) to even print, let alone find.

QED

*Sigh* Probably yet another idiot question poster posting an inaccurate statement of the problem. The guy(s) who said you can't do better than O(n^2) are of course correct. The rest of you who gave O(n) algorithms or can't post a proper question need not apply for any software job ... please. My best guess is that the question was asking for the *sum* over all possible |ai-aj|. Now try to do O(n) for this problem.

I doubt if O(n) is possible. It seems that if this problem could be solved in O(n) sorting could be done in O(n) as well.

If I'm allowed to used extra space,

I would construct an array such that S[i] = Sum(A[0..i]). Takes O(n).

1, 2, 4, 6, 7, 9, 20

|S[i]-S[j]| is the Sum(A[i+1..j]).
|S[i-1]-S[j-1]| is the Sum(A[i..j-1])

i.e,
|S[i]-S[j]| = a[i]+a[i+1]+a[i+2]..+a[j]
|S[i-1]-S[j-1]| = a[i-1]+a[i]+a[i+1]+..+a[j-1]
So,
|S[i]-S[j]| + |S[i-1]-S[j-1]| = |a[i]-a[j]|

Correct me if it's wrong...

-Hari.

there will be n^2 |ai-aj| pairs...wont we need at least n^2 operations to fill those n^2 values in an array.,...i doubt if it could be done in O(n)...

As given array is sorted( assuming descending order) , lets say size of array is 10, a[0,...9]. and the |ai - aj| = x.
Assuming that all numbers are unique in the array ( if they are not this algo can be easily modified). Now define two indexes such that i = 0 and j=1, find the first aj such that either |a0 -aj| = x or |a0 - aj| < x .
Now we have two indexes such that i=0 and j. if |ai - aj| = x then ++j else if |ai-aj|< x then ++i. Follow this procedure and we will get the pairs.

Complexity: O(n)

The solution space is O(n^2), so there is no way to to solve it in O(n).

After yahoo VMWare is also asking for rocket science :P

the minimum time complexity is O(n^2), here is the obvious reason:
say, the array is 1, 2, 3, 4
so all pairs are (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (2, 4),
total number of pairs in this type of input array is !(n-1) = O(n^2)

I could only think of the below given sol. to reduce the matrix into half. Is there a better way to solve the above problem?

for(i=0 to n)
{
j=0;
while((ai-aj)!=0)
{
find(ai-aj);
j++;
}
}

Don't need to process a array location n1 if current array location n2 is greater than n1.

void printDiff(int a[], size_t size)
{
for (unsigned int i = 0; i < size; ++i)
{
for (unsigned int j = i+1; j < size; ++j)
{
cout << i << " , " << j << " = " << abs(a[i] - a[j]) << endl;
}
}
}

Well...if a parallel/vector operations are allowed ... :)
Then, in cycle i=0->N subtract the element i from the rest i+1..N elements - as a one operation - and save results for each step...
Other ideas?

O(nlogn) ??
traverse i till n
find binsearch(|ai-aj|) in rest of the array..
for element 0 u have 10 -10
for element 1 u have 9
for -11 you have 1(this comes before 0)