CODEWITHSUNDEEP
javaarraysalgorithm
Marko Rabrenovic
Marko Rabrenovic

Reputation: 23

Find Two elements in the Array that add up to the Target number in O(n * log n) Time

I have a problem with O(n * log(n)) searching algorithm.

I have to find two numbers from an array that add up to the given number.

I know how O(n * log(n)) works, but I'm not sure if those two correct numbers will meet in search if I do it like this:

for (int i = 0; i < n; i++)
    for (int j = 1; j <= n; j = j*2)

Is there a way to keep O(n * log(n)) complexity so that every two numbers meet in the search?

Upvotes: 1

Views: 703

Answers (1)

kutschkem
kutschkem

Reputation: 8163

  1. sort array (O(nlogn))

  2. for each element:

    2.1 binary search to find other element that adds up to the given number (or to figure out there is none) (O(logn))

Step 2 has complexity O(nlogn), and so the whole algorithm has O(nlogn)

Upvotes: 1

Related Questions