0

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.

3
Contributors
2
Replies
4
Views
7 Years
Discussion Span
Last Post by invisal
0

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

Edited by tesuji: n/a

0

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
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.