Algorithm to sum a triple?

Question

We have an array A with m positive integer numbers, what's an algorithm that will

return true if there's a triple (x,y,z) in A such that A[x] + A[y] + A[z] = 200

Otherwise return false. Numbers in array are distinct and running time must be O(n).

I came up with O(n^3). Any ideas on how to achieve this with O(n)?

Answer 1

Since elements are unique, this boils down to pre processing the array in O(n) to filter redundant elements - which are larger than 200 (none of them will be in the triplet).

Than, you have an array which its size is no larger than 200.

Checking all triplets in this array is O(200^3)=O(1) (it can be done more efficiently in terms of constants though).

So, this will be O(n) U O(200^3) = O(n)