One iteration of quick sort will take O (n)
3rd step will take O (n ^ 2) because .. avrage case.. if you consider that elements are splitted in the middle..
n/2 elements in left side and n/2 elements in right side.... ( they may not be sorted..)
You are againing need to do n/2 * n/2 comparing...
am a wrong sudhakar ????
On 12/20/05, sudhakar-aluri <[EMAIL PROTECTED]> wrote:
my idea is like this:
1/ find a number k in the array where k-z is minimum.
2/ then arrange the array in such a way that array[1...r] contains the
numbers less than z, a[r] contains the k , a[r+1, .. n] contains the
numbers greater than z.
( like one iteration of quick sort, if i remember quciksort properly)
3/ now moving from r to 1 one head and r+1 to n another head, one can
find the possible solutions of x+y =z.
the whole idea is using the "one iteration of quick sort'.
thanks,
sudhakar
Paranthaman Saravanan wrote:
> hey vijay finding the two numbers if the array is sorted is known try to
> find for if the array is not sorted....
> any one can help me in finding this
>
>
> On 12/19/05, Vijay Venkat Raghavan N <[EMAIL PROTECTED]> wrote:
> >
> > Hi,
> >
> > I guess this has already been discuss in this forum before. Anyways let me
> > give my algo here. Let us assume that the array is sorted in ascending order
> > WLOG.
> >
> > let low=1 and high=n index the first and last elements
> > while(low<high)
> > {
> > if a[low]+a[high] == z, done, so break off
> > if a[low]+a[high]<z need to increase sum, so low++;
> > 3rd case, u need to decrease, so high--
> > }
> >
> > hope this helps.
> >
> > -Vijay
> >
> > On 12/19/05, Uppala Babu < [EMAIL PROTECTED]> wrote:
> > >
> > > Hash map takes extra space if you want O(1) search..
> > > Otherwise .. it takes time... any another solution...
> > >
> > > in O(n) time with no extra space.. ;-)
> > >
> > > On 12/19/05, Hemanth < [EMAIL PROTECTED]> wrote:
> > > >
> > > >
> > > > This answer is something like a bit vector based one.
> > > >
> > > > Assume that the array is int[] num.
> > > > for(int i = 0; i < num.length; i++)
> > > > {
> > > > int otherNum = z - num[i];
> > > >
> > > > // Search in a hashmap we maintain for 'otherNum'
> > > > // if 'otherNum' is present, then we are done
> > > > // else add 'num[i]' to the hashmap and proceed
> > > > // to the next iteration.
> > > > }
> > > >
> > > >
> > >
> >
>
>
> --
> Arise awoke stop not till the goal is reached
