##### 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

##### 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:

#!/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)

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