CareerCup

O(n^2)

Sort the array O(nlgn)

c: start from the last element in the array, decrement till it reaches first element
have two pointers - one in the end and one in the beginning.
if the sum of the values at the pointers is greater than the last element, decrement the end pointer
else if the sum is less, increment the first pointer
if equal, print the last element and break
goto c:

what are x and y?

For O(N^2) is easy. Put all the items in a hashtable O(N), then Sort the array O(NlogN) in non-increasing order. Then, choose check the element in order to see if it is the sum of two items in the array. O(N^2). This is just a brutal force solution. Any better ideas?

1. Need to do hashtable.
2. Sort the array in O{N*lgN) first.
3. Check the chosen element to see if it is sum of the any two item. Acturely, this could be O(N^3).
For i= N to 3 (no need to check first two)
do {
for (j= i-1 to 2)
for (k= j-1 to 1)
{
sum = a[j]+a[k];
if a[i] = sum
{ print (i, j, k);
break;
}
}
}
4. If we have enough memories, create an array of N*N/2 to store sum = a[x] + a[y]. This is O(N^2).
Asuming a is sorted in 2.
sum[1] = a[1] + a[2];
sum[2] = a[1] + a[3];
sum[3] = a[2] + a[3];
......
sum[N*N/2] = a[N-1]+ a[N};
This array is sorted because a is sorted.
for i= N to 3
apply binary search on sum for a[i]
This is N* O(lg(N^2)) equals to O(2*N*lgN)

So, the algorithm is O(N*N).
5. You can just do:
s= 0;
do
{
for i= 1 to N-1
for j=i+1 to N
{
temp = a[i] + a[j];
if (temp > sum[s])
{
s++;
sum[s] = temp;
}}}
|
And then, apply binary search to sum (less than N*N/2.

I want to say no need to do hashtable.

Can u please explain the question ?

Divide and Conquer! :)

After sorting the array, you can check A[i] from biggest to smallest and the question became: how to find if there exists a pair of number in an array such that the sum of them is K, in O(logn).

What are x and y

1. first sort array in o(nlog(n)) time.
2. for each S from A[n-1] to A[0], check if there exist two elements in A such that A[x]+A[y] = S. This will take O(n^2) time since for every S, it need O(n) time to find A[x] and A[y].

any better solutions?

1. Sort the array;
2. Starting from the biggest element, say A[n-1], to find if there are a pair of elements A[i] and A[j], whose sum is equal to A[n-1]. The best way is to try A[0]+A[n-1], if smaller than A[n-1], then try A[1]+A[n-1], ..., until two indies meet. It has O(n^2) complexity, and if you use brutal search, it easily goes to O(n^3).

He might have meant maximum sum of a subarray in the array

Or We could sort the array..thats O(nLogn) . and the sum of last two elements is the max sum.
Sounds like too simple, I wonder if I am missing some detail.

the sum(A[i]) is one of the elements in A.

not as simple as that...
here is O(n^2) solution..
first sort the array, for each number find whether there there exists 2 numbers whose sum is equal to that number..find max of them... it is O(n^2) ..
can anyone tell O(nlog(n)) solution??

don't think there is O(nlgn) solution

There is O(nlogn)
1.Sort as Descending
2.If any A[i] == 0 Then the Max is A[0]
3.Omit all negative elements.
4.For A[i] do B[j]=A[i]-A[j];
Check B[j] have the same element of A[i].
If have, Max is A[i]

1.int found=n,t=n,b //n:no of elements in the array
2.QuickSort(A,1,n)
3.while(found>=3) //uptil we reach the case of a[1,2,3 ]
4. for i=1 to t/2
5. b=BinarySearch(A[t]-A[i])
6. if(b==0)
7. found--
8. t--
9. else
break
10.print A[b]"+" A[i] "=" A[t]


Running time===O(n^2)
Best case and avg case are much better

Looks like the nlogn algo does not exist.
Although I did not check carefully.
http://discuss.joelonsoftware.com/default.asp?interview.11.603254.8

sort the array a
ptr1 = length - 2;
ptr2 = length - 3;


while ptr2>=0 {
if a[ptr1] + a[ptr2] = a[ptr1+1] bingo!!
else {
if a[ptr1]+a[ptr2] > a[ptr1+1]
ptr2 -- ;
else
ptr1 --;
ptr2--;
}

complexity is O(nlogn)

This can be done in O(n)...

int A[n], max=A[0],i;
for (i=0;i<n;i++)
{
   if(max <A[i])
   { 
       max = A[i];
    }
}

cout<<"the max value is "<<max;

as the above loop is executed only once, you can find it in O(n).