1 votes 1 votes 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? 3 4 10 64 DS ace-test-series data-structures hashing pigeonhole-principle discrete-mathematics + – Souvik33 asked Oct 30, 2022 Souvik33 404 views answer comment Share Follow See 1 comment See all 1 1 comment reply Shoto commented Oct 30, 2022 reply Follow Share 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 2 votes 2 votes Please log in or register to add a comment.