The Gateway to Computer Science Excellence
+41 votes
4k views

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$
in DS by Veteran (105k points)
edited by | 4k views
+5
Concept of Cyclicity of numbers is used in this question.

3 Answers

+65 votes
Best answer

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$

by Loyal (5.7k points)
edited by
0
What would happen if there is one more function
 $h(i) = 11*i^{3} mod 10$
+5
I like the first sentence
0

In 11*imod 10,all number are not generated. therefore answer is B. In B all numbers are generated and all slots are equally used without any collision. Therewill be coollision in A and other choices. 

0
If we remove 12 from (12*i)mod 10 then ( i mod 10) can also be the answer.
+2
if you divide 11*i^3 mod 10 it would be same as i^3mod10 bcz last digit wont change here as last digit of 11 is 1
0
what happens when the given numbers all are same???
0
what do you mean by all numbers are not generated?
+2
A good hashing function is one which span over entire table..

That means should be capable of generating mapping to all the cells of table.
+34 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)

by Active (4.9k points)
0
Good analysis.
0
What about number starting from 11 to 2020?
0
same logic would be apply
0
Correct observation.
0
Can you give a hint of how to use power cycle concept here?

Also,in you analysis of option d,4,6 are no repeating
0
Well explained
+8 votes

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

by Boss (13.5k points)
+2
So what is the significance of 2020 here ?
+3
No significance
+2
yes , I think there is a significance. If first 10 number equally distributed among 0-9, then all other number also equally distributed among 0-9.

Otherwise it will not equally distributed among 0-9
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,617 answers
195,897 comments
102,350 users