Ace Academy Test Series Qn#7

Question

A hash function h maps 16-bit inputs to 8 bit hash values. What is the largest k such that in any set of 1000 inputs, there are atleast k inputs that h maps to the same hash value?

1. 3
2. 4
3. 10
4. 64

Comments

We can map 16 bit input to 8 bit hash value, so size of hash table = $2^8 = 256$

Apply pigeonhole principle, there are 1000 pigeons and 256 holes

So one hole will definitely have 4 pigeons, hence (b) is the answer