Algorithmic problem
Author
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 :)
You could make some tweaks ...
"& lt;" stands for "<"
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 "<"
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:
And, if you feel like cheating, you can use radix sort on integers to get an O(n) 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.
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?
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?
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
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
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:
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
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
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 = 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.
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).
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 :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
