# Algorithmic problem

This topic is 4858 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

This problem is from a book, and it's marked with an asterisk, which means it is special/hard. From the second chapter (getting started): Describe an O(nlogn)-time algorithm that, given a set S of n integers and another integer x,determines whether or not there exists two elements in S whose sum is exactly x. Here's my try: 1) you sort the numbers is S -> nlogn 2) for each number in S -> n 3) you binary_search for (x-that_number) in the set -> logn ----- Sum: nlong + n*logn = 2nlogn == O(nlogn) Is that right? My book is the TCRC book and we are calling the O-notation as Th-notetion btw, because we are still in the beginning. ..So are there any faster solutions? ( there is the n^2 solution and the n*(n+1)/2 solutions, but they are not fast ) thanks in advance guys :)

##### Share on other sites
You could make some tweaks ...

after sorting  (small to large) :if ( S_n + S_(n-1) < x  ) then no such 2 elementselse if ( S_1 + S_2 > x ) then no such 2 elementsand searching might be done a little different  :i1 = 1 i2 = 2for ( i2 <= n ){  x' = x - S_i1;  while ( ( S_i2 < x' ) && ( i2 <= n ) )  {     i2++;  }  if (  x'  == x )  {         succes , present....  }     i1++; }

"& lt;" stands for "<"

##### Share on other sites
Your version is correct, but you don't need binary searching. Once the array is sorted in increasing order, you can simply apply the following algorithm:

i = 0j = n-1while i < j do  if S+S[j] = x then return FOUND  else if S+S[j] > x then decrease j  else increase i donereturn NOT FOUND

And, if you feel like cheating, you can use radix sort on integers to get an O(n) algorithm.

##### Share on other sites
hi again this is valla2. thanks guys for the replies!
About PGC's post, i don't really understand what he is doing...

About ToohVryk, your alrorithm for finding out if there are 2 integers whose sum is x is ok, but your searching method has O(n) running time complexity, and that would make the algorithm O(n^2), instead of O(nlogn) when using binary_search whose complexity is O(logn).

..so?

##### Share on other sites
Hi!

1) As proposed sort the numbers
2) Assume we now have S[1] ... S[N] in increasing order:

i := 0;
j := 0;
sum := 0;

while ((i x) {
sum -= S;
i++;
}}
3) Complexity argumentation:
The while loop is terminating as in each loop we increment i or j or exit. Sorting (e.g. quicksort) is done in O(N log N) (or can be even done in linear time with bucket sort or radix sort for a fixed number of integers). The above shown program is linear, as neither i nor j can go back. => we have a O(N log N) algorithm.

Ingo

##### Share on other sites
Hi!

Sorry, above message text was mixed up (forget to escape HTML special characters).

1) As proposed sort the numbers
2) Assume we now have S[1] ... S[N] in increasing order:
i := 0;j := 0;sum := 0;while ((i < N) && (j < N)) {if (sum == x)    exit("FOUND");if (sum < x) {    j++;    sum += S[j];}if (sum > x) {    sum -= S;    i++;}}exit("NOT FOUND")

3) Complexity argumentation:
The while loop is terminating as in each loop we increment i or j or exit. Sorting (e.g. quicksort) is done in O(N log N) (or can be even done in linear time with bucket sort or radix sort for a fixed number of integers). The above shown program is linear, as neither i nor j can go back. => we have a O(N log N) algorithm.

Ingo

##### Share on other sites
Quote:
 Original post by ToohrVykYour version is correct, but you don't need binary searching. Once the array is sorted in increasing order, you can simply apply the following algorithm:i = 0j = n-1while i < j do if S+S[j] = x then return FOUND else if S+S[j] > x then decrease j else increase i donereturn NOT FOUNDAnd, if you feel like cheating, you can use radix sort on integers to get an O(n) algorithm.

This looks to me like:
1) you sort: O(n) or O(nlogn)
2) you call the above code only once: O(n)
so you have a total of only O(n).

##### Share on other sites

this is valla2

Thanks A LOT! YOu guys are so great! Now i get it with the code of ToohrVyk! Thanks that's the best solution i saw so far, great algorithm!

@Anonymous Poster: your algorithm has a little problem. If x is 6 and S = { 1,2,3} then your algo will return "FOUND" because 1+2+3 = 6. We only want 2 numbers. YOur program is the solution to a problem that would ask us to find weather or not we can form X with (1) any, (2) consecutive integers from S.

thanks again guys :)

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 10
• 23
• 12
• 12
• 11
• ### Forum Statistics

• Total Topics
634779
• Total Posts
3019241
×