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.

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

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
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.