# Coding Interview Problem #1

## Problem Statement

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

## Example

Given, input of [10, 15, 3, 7] and k of 17, the method returns true. Since 10 + 7 is 17.

### Bonus

Can you do this in one pass?

## Brute Force Solution

Nested iteration is used to check for every pair of numbers. [10,15], [10, 3], [10,7], [15, 3], [15, 7] and [3,7].

```
def add_upto?(input, k)
for i in (0..(input.size-1))
for j in (0..(input.size-1))
return true if i != j and input[i]+input[j] == k
end
end
false
end
input = [10, 15, 3, 7]
k = 17
result = add_upto?(input, k)
puts result
```

Performance: We have nested loops (two), so it is O of N square.

### Variation

We can return i,j instead of return true for the variation on this problem that requires indices as the output.

## One Pass Solution Using Array

17 - 10 = 7. Is 7 in the list? We can check if (k - element) = x is in the list or not.

```
def add_up?(input, k)
input.each do |element|
if input.include?(k - element)
return true
end
end
false
end
p add_up?([10,15,3,7], 17)
```

Performance is O(N).

## One Pass Solution Using Set

Use a set to remember the number we have seen so far. Then for a given number, we can check if there is another number that if added would sum to k.

Iteration | set | element | k - element |
---|---|---|---|

1 | {}, 10 | 10 | 7 |

2 | 10, {10,15} | 15 | 2 |

3 | {10,15}, {10.15,3} | 3 | 14 |

4 | {10.15,3} | 7 | 10 |

The set column as the beginning and the end values of the set as we iterate through the list.

```
require 'set'
def add_up?(input, k)
set = Set.new
input.each do |element|
if set.member?(k - element)
return true
end
set.add(element)
end
false
end
p add_up?([10,15,3,7], 17)
```

If you trace the values of the variables, you can see that we look in the reverse direction. Performance is O(N).

## Solution Using Binary Search

- Sort the list
- Iterate through the list. Run binary search on k - list[i].

We binary search N elements, so performance is O(N log N) and space is O(1).

# Related Articles

# Ace the Technical Interview

- Easily find the gaps in your knowledge
- Get customized lessons based on where you are
- Take consistent action everyday
- Builtin accountability to keep you on track
- You will solve bigger problems over time
- Get the job of your dreams

#### Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview