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?
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
#!/usr/bin/py def solveMissing(n, m): n_cnt =  * 101 m_cnt =  * 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.