HackerRank ‘Missing Numbers’ Solution

H
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?

Link

Sherlock and Array

Complexity:

time complexity is O(n)

space complexity is O(n)

Execution:

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

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/py
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)

About the author

Add comment

Archives

Categories