We say that the numbers, `a`

and `b`

, are a perfect match to `target`

if their sum equals to target; That is: `a+b=target`

. In the following Facebook interview question we use this definition.

## How to Find The Perfect Match to Target in a List

Given a list of numbers and target, find in the list two numbers that are perfect match to target. If such numbers exist, return their indexes in the list as a tuple in ascending order. Otherwise, return `None`

.

### Sample 1

Suppose the `target`

is `7`

and the list is `[0,1,2,3,4,5,6,7]`

then we can return one of `(0,7)`

,`(1,6)`

,`(2,5)`

,`(3,4)`

### Sample 2

Suppose the target is `14`

and the list is `[0,1,2,3,4,5,6,7]`

, then we must return `None`

since there are no two numbers in the list that are a perfect match to the target.

## Solution #1: Naive `O(N`^{2})

Solution

^{2})

Suppose we have a list of numbers `A`

with `N`

items. You can quickly iterate over all possible pairs in the list and check whether their sum equals to target. If we found such pairs, return their indexes; otherwise, we return `None`

.

How can we find all possible pairs in a list?

The first observation is that any possible pair can be represented by the tuple `(x,y)`

if `0≤x<N`

and `0≤y<N`

. Suppose `a=A[x]`

and `b=A[y]`

, then we can represent the numbers `a`

and `b`

as the tuple `(x,y)`

. In other words, we can map the pair `a`

and `b`

by their corresponding positions in the list.

Well, It seems a straightforward task.

```
def findPerfect(numbers: List[int], target: int) -> Union[Tuple[int,int],None]:
def ArePerfect(aa: int , bb: int, target: int) -> bool:
return target == (aa+bb)
size = len(numbers)
for xx in range(0,size):
for yy in range(0,size):
if ArePerfect(numbers[xx], numbers[yy], target):
return (xx,yy)
return None
```

We have `N`

possible pairs to check. In other words, the algorithm runtime is ^{2}`O(N`

^{2})

## Solution #2: Fixing the Solution 1

Well, We are in the right direction to solve this Facebook interview question. But there is bug in the above solution. Can you find it?

The error is that while any possible pair can be represented by the tuple `(x,y)`

if `0≤x<N`

and `0≤y<N`

, the opposite is not valid. That is, not all tuples `(x,y)`

where `0≤x<N`

and `0≤y<N`

maps to a valid pair. If `x=y`

, the tuple `(x,y)`

does not map to a valid pair. Why? if `x=y`

then we have a pair with the same item, however, we want to find two different items in the list. Let’s fix it to eliminate the pairs from the form `(x,x)`

:

```
def findPerfect(numbers: List[int], target: int) -> Union[Tuple[int,int],None]:
def ArePerfect(aa: int , bb: int, target: int) -> bool:
return target == (aa+bb)
size = len(numbers)
for xx in range(0,size):
for yy in range(0,size):
if xx != yy and ArePerfect(numbers[xx], numbers[yy], target):
return (xx,yy)
return None
```

Now, the solution is correct. We now check only `N(N-1)`

pairs. But the algorithm runtime is still `O(N`

. Can you improve it?^{2})

**Solution #3:** Sum Operator is Symmetric

In our case we there is no importance to the order of the numbers. We all know that the sum operator is symmetric, in other words a+b=b+a, Therefore if the pair represented by the pair represented by tuple `(x,y)`

is perfect match to target, then the pair represented by`(y,x)`

is also perfect match to target.

Let’s update our observation: We need to check all tuples `(x,y)`

where `0≤x<N`

and `x+1≤y<N`

. In other words, all the tuples where `y`

is smaller than `x`

. This way, we will check all valid pairs at least once and only once. First, we eliminate the invalid pairs from the form `(x,x)`

. second, we eliminate the valid `(p,q)`

where` p>q`

since we will check this pair when we process the tuple `(q,p)`

Let’s update the the code:

```
def findPerfect(numbers: List[int], target: int) -> Union[Tuple[int,int],None]:
def ArePerfect(aa: int , bb: int, target: int) -> bool:
return target == (aa+bb)
for xx in range(0,len(numbers)):
for yy in range(xx+1,len(numbers)):
if ArePerfect(numbers[xx], numbers[yy], target):
return (xx,yy)
return None
```

We decrease the numbers of pairs we need to N(N-1)/2 pairs. We optimize the checking but it is still O(n^2) algorithm.

## Conclusions For Perfect Match Facebook Interview Question

In the last operation, we use the observation that the sum operator is symmetric. However, not all the operators are symmetric. Suppose we change the definition: We say that the numbers, a and b, are a perfect match to `target`

if `a`

. This claim does not hold anymore. For example: ^{b} = target`2`

while 3^{3}=8^{2}=9.

We decrease the numbers of pairs, we need to check by using the symmetric property observation. However, the algorithm runtime is still O(N^2). The naive solution works, However, There is better solution to this Facebook interview question, Can you find another observation about what we want to find in the list and improve the runtime of the solution?