Mike,
>>>>>>>>>>
*This solution is much easier if I was programming in c/c++ where I could *use pointers. We'll wing it tho ;) Really, what I want to do is have a *pointer to the max_element and one to the min_element, and then if their *sum is greater then x, I decrease the max_element, if their sum is less *then X I increase the min_element, if their sum equal X I end. One final
*case, our end case, if max_element = min_element and max_ele + min_ele != *X, I return failure.
max_index = k
min_index = 1
do while arr(max_index)+arr(min_index) != X
if arr(max_index)+arr(min_index) > X
max_index = max_index - 1
else if arr(max_index)+arr(min_index) < X
min_index = min_index + 1
else if arr(max_index) = arr(min_index)&&we already know their sum doesn't
&&equal X, that's tested by our * &&our while loop
return "Failure!"
endif
enddo
Worst case, the entire array is scanned, or O(n) - linear running time.
im almost absolutely sure this works,
>>>>>>>>>>
Bingo! Your solution is correct with one exception. I did not specify the array must contain two numbers that sum to X. Changing your do while to include an additional condition to check min_index < max_index - and returning a no match exists if ever false - solves the problem.
The proof is a little bit tricky because it involves proving that any rejected by the algorithm cannot be part of the solution.
Congratulations!
Daniel
Précédent
Suivant
Répondre
Voir le fil de ce thread
Voir le fil de ce thread à partir de ce message seulement
Voir tous les messages de ce thread
Voir tous les messages de ce thread à partir de ce message seulement