what can be optimal solution for problem?

Question

Let there be an array: [6,9,2,4,1]

I need to find if input number have a pair or not.
Ex. Input - 7
Output - Yes (6+1 )

Input - 16
Output - No (no pair addition is 16)

I know the obvious way by running 2 loops but it have time complexity n^2 . Can someone help me with some optimized solutions ?
Programming Language : Java

What I tried : 1) Sort array
2) Based on input number divide it into 2 subarray (input/2).
3) Inner loop on first array and outer loop on second

This reduces iterations.

You could do it with 1 loop, eg: foreach(var i in array) { if (array.contains( input-i)) { //combination found break; } } — Luc, Nov 21 '18 at 12:54
You could sort and use 2 pointers. Time Complexity is O(n log(n)) with space O(1). You can also use a HashMap which will have time complexity O(n) with space O(n). It's up to you to trade time for space or vice versa. — nice_dev, Nov 21 '18 at 12:57
@Luc: `array.Contains` needs to lookup the data which includes looping through it... — Markus Safar, Nov 21 '18 at 13:04
1. Initialize a empty hashset . 2. Run a loop and check if(hashset.contains(num - arr[i]){ return "Yes"} hashset.add(arr[i]) 3. End of loop return "No" — Code_Eat_Sleep, Nov 22 '18 at 01:30

Berthur · Answer 1 · 2018-11-21T13:10:54.370

Consider the same problem if your list was sorted. Then it becomes much easier to figure out whether there is a pair in the list which sums up to Input or not. Here's a high-level description of an algorithm you could use:

Sort your array
Set up two pointers l on the leftmost element and r on the rightmost
Move the pointers inwards one at a time, using something like the while-loop below:

As follows (pseudocode):

l = 0
r = length(Input) - 1
while l < r:
    if (arr[l] + arr[r] == Input) return (arr[l], arr[r])
    else if (arr[l] + arr[r] < Input) l = l+1
    else r = r-1
return NULL

The loop itself is linear (O(n)), and the sorting can be done in O(n*log n) time. Thus the complexity of the whole algorithm would be O(n + n*log n) = O(n*log(n)).

score 0 · Answer 2 · answered Nov 22 '18 at 00:13

Nested for loops is O(n^2). Sorting is O(nlogn). How about this O(n) approach:

1) Create a Hashed Set of the array 2) Iterate through the array once, checking at each index i if value-arr[i] is in the set.

Example:

values = set(array) 
for i in array:
     if 7 - i in values:
          return i, 7-i

what can be optimal solution for problem?

2 Answers2