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