Given a vector of maximum 10 000 natural and distinct numbers, find 4 numbers(a, b, c, d) such that
- by king_kong
Hi,
I solved this problem by following a straightforward but not optimal algorithm. I sorted the vector in descending order and after that substracted numbers from max to min to see if I get a + b + c = d.
Notice that I haven't used anywhere the fact that elements are natural, distinct and 10 000 at most. I suppose these details are the key.
Does anyone here have a hint over an optimal way of solving this?
Thank you in advance!
Later Edit:
My idea goes like this:
'<<quicksort in descending order>>'
for i:=0 to count { // after sorting, loop through the array
int d := v[i];
for j:=i+1 to count {
int dif1 := d - v[j];
int a := v[j];
for k:=j+1 to count {
if (v[k] > dif1)
continue;
int dif2 := dif1 - v[k];
b := v[k];
for l:=k+1 to count {
if (dif2 = v[l]) {
c := dif2;
return {a, b, c, d}
}
}
}
}
}
What do you think?(sorry for the bad indentation)
