None Interview Question
StudentsCountry: 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