Find a Missing Number

From Software Engineers Wiki
Jump to: navigation, search

A set of integer has all integer values in certain range but one. Find which number is missing.

Answer #1

One way is to calculate expected sum of all the numbers int the range, then subtract the all the numbers in the set. The difference will be missing number. But this approach has one issue; the sum may overflow. Extra care needs to be done to take care of the overflow. For example, it may not calculate sum of all numbers in the beginning, it may alternate adding and subtractions as necessary.

Answer #2

If all the elements in an array is unique, only one number is missing out of 0..N in N-1 sized array, we can take advantage of the property of XOR operation. If XOR operations are done twice for any given number, it becomes original number. If the array is [0, 1, 3, 4].

all_xors = 0 ^ 1 ^ 2 ^ 3 ^ 4;

Then do XORs with each element.

all_xors ^ 0 ^ 1 ^ 3 ^ 4

All XORs cancel out except 2. This is practically same as all_xors = 0 ^ 2. So the result is 2.

Simple function written in python.

def find_miss_one(num_array):
        all_xors = 0
        N = len(num_array) 
        for i in range(N + 1):
                all_xors ^= i
        for i in range(N):
                all_xors ^= num_array[i]
        return all_xors

Test program:

def main():
        A = [ 0, 1, 3, 4, 9, 5, 7, 6, 2 ]

Personal tools