- Prepare
- Algorithms
- Search
- Missing Numbers
- Discussions

# Missing Numbers

# Missing Numbers

+ 50 comments A simple solution i would think of is,

STEP-1: Create a array initially with size 10001 with all zeros.

STEP-2: We are going to decrement the value corresponding to the value that we read as input.

`for example if the first element of list A is 200, then array[200]--.`

. Similarly we decrement the values for list A.STEP-3: Similarly when reading list B increment the values. Since the elements of list A are lost, the resulting values in the array after this operation will be positive.

STEP-4: Print all the index of array with value grater than 0. The numbers will be in asscending order aswell.

This solution can be optimized in a number of ways. Hint is "

`Xmax−Xmin<101`

".Happy Coding!!

+ 5 comments Java users note that if you're using HashMap to represent number frequencies, make sure you use the .equals() method to compare them and not == because Integer is an object while int is a primitive, that was causing me WA

+ 8 comments in Python, if you know Counter from the standard collection library, you can do:

def missingNumbers(arr, brr): a = Counter(arr) b = Counter(brr) return sorted((b - a).keys())

Not sure why this question worth 45 points, its even much eaiser than some of those 15/20 points questions.

+ 3 comments # Simple in Python 3 :-)

from collections import Counter n,arr=int(input()),list(map(int,input().split())) m,brr=int(input()),list(map(int,input().split())) a,b=Counter(arr),Counter(brr) print(*(sorted((b-a).keys())))

# Explanation:

Let us take an example : n=10 arr=11 4 11 7 13 4 12 11 10 14 m=15 brr=11 4 11 7 3 7 10 13 4 8 12 11 10 14 12 a=Counter(arr)=Counter({11: 3, 4: 2, 7: 1, 13: 1, 12: 1, 10: 1, 14: 1}) b=Counter(brr)=Counter({11: 3, 4: 2, 7: 2, 10: 2, 12: 2, 3: 1, 13: 1, 8: 1, 14: 1}) b-a=Counter({7: 1, 3: 1, 10: 1, 8: 1, 12: 1}) (b-a).keys()=dict_keys([7, 3, 10, 8, 12]) sorted((b-a).keys())=3 7 8 10 12

+ 6 comments `The difference between maximum and minimum number in the list B is less than or equal to 100`

- this actually gave the clue away for solving this problem, without which the problem would have been much harder.

Sort 1069 Discussions, By:

Please Login in order to post a comment