Jump to content
  • Advertisement
Sign in to follow this  
valla2

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
You could make some tweaks ...



after sorting (small to large) :
if ( S_n + S_(n-1) < x ) then no such 2 elements
else if ( S_1 + S_2 > x ) then no such 2 elements

and searching might be done a little different :
i1 = 1
i2 = 2

for ( i2 <= n )
{
x' = x - S_i1;

while ( ( S_i2 < x' ) && ( i2 <= n ) )
{
i2++;
}

if ( x' == x )
{
succes , present....
}

i1++;
}






"& lt;" stands for "<"

Share this post


Link to post
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 = 0
j = n-1

while i < j do

if S+S[j] = x then return FOUND
else if S+S[j] > x then decrease j
else increase i

done

return NOT FOUND


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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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++;
}}
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
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 = 0
j = n-1

while i < j do

if S+S[j] = x then return FOUND
else if S+S[j] > x then decrease j
else increase i

done

return NOT FOUND


And, 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 this post


Link to post
Share on other sites
Guest Anonymous Poster

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 :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!