4.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
edited | 4.4k views
+6
Concept of Cyclicity of numbers is used in this question.

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.8k points)
edited
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.
+3
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.

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)

by Active (5k 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

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

by Boss (13.7k 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
0

Whenever GATE gives you a question with a very large value, there's almost always a pattern to that problem, which could be understood by taking smaller values.

Last month while practicing Graph Theory, I found a 2018 question that included a graph on $100!$ vertices, which blew my mind when I first read it. But I ended up solving it just by keeping $n=2 \ and \ 3$.