[algogeeks] Re: find the sum

Mon, 07 Aug 2006 17:03:07 -0700

Oh, that's true, it is O(n), ... thanks.

 
On 8/7/06, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]> wrote:

Bruce Yang has the right O(n)N algorithm. Basically it is:

1. Have two pointers ptr1 = arr[0] and ptr2 = arr[ n - 1].
2. While (!found && ptr1 < ptr2)
   a. sum = ptr1 + ptr2
  b. if (sum == req_sum)
        found the numbers .. ptr1 and ptr2
   c. if (sum < req_sum)
        Increment ptr1
   d. if (sum > req_sum)
       Decrement ptr2

-Dhyanesh

On 8/7/06, Lego Haryanto <[EMAIL PROTECTED]> wrote:
>
> I'm not sure if we can find an O(n) algorithm for this, but there is an
> improvement to your O(n lg n) algorithm, which basically limits your binary
> search scope each time we scan each number.
>
> For instance, in the set of 1, 3, 7, 9, 16, 28, 49 and x=16, ... we start
> with a scope of the whole S except for the first one [3,7,9,16,28,49]
> subject to binary search.
>
> When we see the first number (1), we know for sure we're looking for 15
> (which is 16-1), so when we binary search and we can't find 15, we should
> narrow down the search scope to the upper limit of 9 for the next number
> (there is no reason to include 16, 28, and 49 for the next search since the
> next number we scan will definitely be greater than 1).  So, we set 9 as our
> upper limit.
>
> When the next number (3) comes, we don't even need to binary search because
> our search range is only [7, 9], and 13 is definitely out of range.
>
> Note that the lower limit for the binary search set can always be set to the
> next-neighbor of the number being evaluated.
>
> Eventually, the algorithm will find the desired pair, or the algorithm
> terminates because lower-limit is greater than upper-limit, which means
> there's no such pair.
>
> Please confirm.
>
>
> On 8/7/06, ravi <[EMAIL PROTECTED]> wrote:
> >
> > The input is an array S  containing n real numbers, and a real number
> > x, Design an algorithm to determine whether there are 2 elements of S
> > whose sum is exactly x.  and onemore thing is that S is in sorted
> > order.
> >
> > I got the solution with the complexity of O(n logn) but I am searching
> > for an algo. on O(n) complexity.
> >
> > My solution is like this,
> >
> > for each element k in S           // There are n element so iterates n
> > times
> > {
> >          k = k - x;
> >          if( BinarySearch(k,S) )  // complexity is O ( log n )
> >         {
> >                 found an elemnt
> >                 break;
> >         }
> > }
> >
> > So overall complexity is O ( n logn).
> >
> >
> >
> >
> >
>
>
>
> --
> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
>
>  >
>




--
Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---

Reply via email to