dimanche 5 mai 2019

Find whether a pair sums to a given target in one pass

I am trying to solve the following question:

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

I am interested in the bonus question.

I think I am able to do it in one pass and in O(k) space. However, I must assume that the numbers are positive and the all the numbers x in the given array satisfy -1 < x < k + 1.

I do it by creating a bool array of size k + 1 and marking true the differences between each element and k. If I ever arrive at an element in the array that has been marked "true," I return true. If not, I return false.

Do you think it is possible to do it in one pass without any assumptions?

If you want to provide your solution, feel free! Just tell me that is what you are giving me so that I may first try to solve it myself before I look to see what you have written.

Aucun commentaire:

Enregistrer un commentaire