HackerRank ‘Missing Numbers’ Solution

Short Problem Definition:

Numeros, the Artist, had two lists A and B, such that B was a permutation of A. Numeros was very proud of these lists. Unfortunately, while transporting them from one exhibition to another, some numbers from A got left out. Can you find the numbers missing?


Sherlock and Array


time complexity is O(n)

space complexity is O(n)


The problem statement informs us, that there are only 100 different values. This calls for a counting sort.0

def solveMissing(n, m):
    n_cnt = [0] * 101
    m_cnt = [0] * 101
    offset = min(m)
    for ele in m:
        m_cnt[ele-offset] += 1
    for ele in n:
        n_cnt[ele-offset] += 1
    for idx in xrange(101):
        if m_cnt[idx] != n_cnt[idx]:
            print idx + offset,
if __name__ == '__main__':
    n = int(raw_input())
    arr = map(int, raw_input().split())
    m = int(raw_input())
    arr2 = map(int, raw_input().split())
    solveMissing(arr, arr2)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.