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.
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
}