## None Interview Question

Students**Country:**India

**Interview Type:**Written Test

Typical way to do it is sort the list first and iterate to find the dups and missing numbers. This is python solution without checking the integrity of the input list. For your homework you might wanna do the check.

```
def foo(l):
missing = None
dup = None
l.sort()
for i in range(len(l)-1):
if l[i]==l[i+1]:
missing = l[i]
elif l[i]==l[i+1]-2:
dup = l[i]+1
return (missing, dup)
```

O(n)

```
def findMissingAndRepeat(sequence):
helperArray = [0 for x in range(len(sequence))]
for num in sequence:
helperArray[num-1] += 1
for i in range(len(helperArray)):
if helperArray[i] == 0:
print '{} is missing'.format(i+1)
if helperArray[i] == 2:
print '{} is repeated'.format(i+1)
print findMissingAndRepeat([3, 1, 5, 8, 8, 7, 6, 2, 4]) # 8 repeated, 9 missing
```

sum of the numbers from 1 to n is n(n+1)/2

- Anonymous February 25, 2015sum of the squares of the numbers from 1 to n is n(n+1)(2n+1)/6

passing through the array adding numbers and squares gives us conditions on m - d and m^2-d^2, where m is the missing value and d the duplicate. Then it is just trivial to find both m and d. You do the math. :)

O(n) time and O(1) space