if there exists two elements in array whose sum is x

[vivek01anand]

there are N elements in an array. u have one number x. u have to check whether there exists two elements in that array whose sum is x. But order should be less than N^2( N square).

i dont know the method how to achieve order less than n^2.

[tesuji]

Hello

Not really sure whether it will work:

1. Sort the array by a method O(n log n), for example by heap or quick sort

2. Then access the array elements by bisection method, O(log n).

-- tesu

[invisal]

If you know the range of numbers in the array, you can take the advantage of this knowledge to find whether there exists two elements whose sum X in linear time O(n).

For example: X is 7 and I have this array called Array A:
5 1 2 4 3 8 1 4 0 7

I know the range of numbers which is from 0 to 8. So I allocate another array of this length called Array B. Each element of Array B represents number of its index occurring in Array A.

Then, I run through each element of Array A again. To find whether there exists two elements whose sum X, you can simply:

if (ArrayB[X-ArrayA[i]] > 0) {
    // exists
}