edited by
16,840 views
72 votes
72 votes

Which one of the following hash functions  on integers will distribute keys most uniformly over $10$ buckets numbered $0$ to $9$ for $i$ ranging from $0$ to $2020$?

  1. $h(i) = i^2 \text{mod } 10$
  2. $h(i) = i^3 \text{mod } 10$
  3. $h(i) = (11 \ast i^2) \text{mod } 10$
  4. $h(i) = (12 \ast i^2) \text{mod } 10$
edited by

4 Answers

Best answer
112 votes
112 votes

Since mod $10$ is used, the last digit matters.

If we CUBE all numbers from $0$ to $9$, we get the following

$\begin{array}{ccc} \textbf{Number} & \textbf{Cube} & \textbf{Last Digit in Cube} \\  \text{0} & \text{0} & \text{0} \\  \text{1} & \text{1} & \text{1} \\  \text{2} & \text{8} & \text{8} \\  \text{3} & \text{27} & \text{7} \\  \text{4} & \text{64} & \text{4} \\ \text{5} & \text{125} & \text{5} \\  \text{6} & \text{216} & \text{6} \\  \text{7} & \text{343} & \text{3} \\  \text{8} & \text{512} & \text{2} \\  \text{9} & \text{729} & \text{9} \\   \end{array}$

Therefore all numbers from $0$ to $2020$ are equally divided in to $10$ buckets. If we make a table for square, we won't get equal distribution as shown in the following table. $1, 4, 6$ and $9$ are repeated, so these buckets would have more entries and there are no buckets corresponding to $2, 3, 7$ and $8.$

$\begin{array}{ccc} \textbf{Number} & \textbf{Square} & \textbf{Last Digit in Cube} \\  \text{0} & \text{0} & \text{0} \\  \text{1} & \text{1} & \textbf{1} \\  \text{2} & \text{4} & \textbf{4} \\  \text{3} & \text{9} & \textbf{9} \\  \text{4} & \text{16} & \textbf{6} \\ \text{5} & \text{25} & \text{5} \\  \text{6} & \text{36} & \textbf{6} \\  \text{7} & \text{49} & \textbf{9} \\  \text{8} & \text{64} & \textbf{4} \\  \text{9} & \text{81} & \textbf{1} \\   \end{array}$

http://geeksquiz.com/gate-gate-cs-2015-set-2-question-43/

Correct Answer: $B$

edited by
61 votes
61 votes

This is aptitude question, actually! (concept of power cycle will be helpful)

a) (0,1,4,9,6,5,6,9,4,1,0) repeated [Not including 2,3,7,8] (loss of 4)

b) (0,1,8,7,4,5,6,3,2,9) repeated [Includes everyone]

c) (0,1,4,9,6,5,6,9,4,1,0) repeated [Not including 2,3,7,8] (loss of 4)

d) (0,2,4,6,8) repeated [Not inluding any odd nos.](loss of 5)

Answer is (B)

11 votes
11 votes

Ans B, all numbers are generated in this, if you have any doubt check this 

0 votes
0 votes

Alternative approach – 
Using the concept of power of cycle: 

(a) (0,1,4,9,6,5,6,9,4,1,0) repeated 
(b) (0,1,8,7,4,5,6,3,2,9) repeated 
(c) (0,1,4,9,6,5,6,9,4,1,0) repeated 
(d) (0,2,4,6,8) repeated 

So, only h(i) =i3 mod 10 covers all the digits from 0 to 9. 
Hence Option (C) is correct. answer 

Answer:

Related questions

62 votes
62 votes
4 answers
1
go_editor asked Feb 12, 2015
16,018 views
Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is...
35 votes
35 votes
12 answers
2
go_editor asked Feb 12, 2015
30,005 views
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.