GATE CSE 2015 | Set 2 | Question: 33

Question

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$?

• A. $h(i) = i^2 \text{mod } 10$
• B. $h(i) = i^3 \text{mod } 10$
• C. $h(i) = (11 \ast i^2) \text{mod } 10$
• D. $h(i) = (12 \ast i^2) \text{mod } 10$

Comments

Also, eliminate (D) as multiplication by 12 ensures that only even number buckets are used.

---

Use cyclicity of last digits

• Squares repeat in limited residues.

• Cubes modulo 10 produce all digits.

---

https://youtu.be/804ML4KSmVc?si=o5afQFQwkJGeCQhs&t=1257

Answer 1

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$

Comments

$(\text{Any number})^3\ mod\ 10 \equiv\ n^3 \ mod\ 10 $, where $n \in \{0,1,2,3,4,5,6,7,8,9\}$

For example, $(2099)^3\ mod\ 10=[(2099\ mod\ 10 )*(2099\ mod\ 10 )*(2099\ mod\ 10 )]\ mod\ 10$

$=(9*9*9)\ mod\ 10=81\ mod\ 10=1$

As $0$ to $9$ numbers are are equally divided in to  buckets,

Therefore all numbers from $0$ to $2020$ are equally divided in to  buckets.

---

Helpful....

---

there is a calculation mistake in this: (2099)^3 mod 10 = 9

Answer 2

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)

Comments

Well explained

---

nicely explained

---

great !!!

Answer 3

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

Comments

So what is the significance of 2020 here ?

---

No significance

---

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

---

Vishesh Bajpai 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$.

Answer 4

We are given four candidate hash functions and asked to determine which one distributes the keys $i = 0, 1, 2, \dots, 2020$ most uniformly across 10 buckets labeled $0$ through $9$. A uniform distribution means that each bucket receives approximately the same number of keys. Since the total number of keys is $2021$, an ideal hash function would assign either $\lfloor 2021/10 \rfloor = 202$ or $\lceil 2021/10 \rceil = 203$ keys to each bucket.

Because all candidate functions are defined modulo $10$, their behavior is periodic with period $10$. Thus, it suffices to examine the output of each function for $i = 0$ to $9$; the pattern will repeat every 10 inputs. Over $2021$ keys, there are $202$ complete cycles of $10$ (covering $i = 0$ to $2019$) and one extra value ($i = 2020$). Therefore, uniformity is determined by how many distinct residues modulo $10$ each function produces and whether those residues are equally frequent within one period.

We now analyze each option.

Option A: $h(i) = i^2 \mod 10$

Compute $i^2 \mod 10$ for $i = 0$ to $9$:

\[
\begin{array}{|c|c|c|}
\hline
i & i^2 & i^2 \mod 10 \\
\hline
0 & 0 & 0 \\
1 & 1 & 1 \\
2 & 4 & 4 \\
3 & 9 & 9 \\
4 & 16 & 6 \\
5 & 25 & 5 \\
6 & 36 & 6 \\
7 & 49 & 9 \\
8 & 64 & 4 \\
9 & 81 & 1 \\
\hline
\end{array}
\]

 

The set of residues is ${0, 1, 4, 5, 6, 9}$ — only 6 distinct buckets are used. Buckets $2, 3, 7, 8$ never receive any keys. Hence, the distribution is highly non-uniform.

Option B: $h(i) = i^3 \mod 10$

Compute $i^3 \mod 10$ for $i = 0$ to $9$:

\[
\begin{array}{|c|c|c|}
\hline
i & i^3 & i^3 \mod 10 \\
\hline
0 & 0 & 0 \\
1 & 1 & 1 \\
2 & 8 & 8 \\
3 & 27 & 7 \\
4 & 64 & 4 \\
5 & 125 & 5 \\
6 & 216 & 6 \\
7 & 343 & 3 \\
8 & 512 & 2 \\
9 & 729 & 9 \\
\hline
\end{array}
\]
 

The residues are ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ — all 10 buckets appear exactly once in each period of 10. Therefore, over 202 full periods, each bucket receives exactly 202 keys. The final key ($i = 2020$) satisfies $2020 \equiv 0 \pmod{10}$, so $h(2020) = 0^3 \mod 10 = 0$, giving bucket $0$ one extra key (total 203). All other buckets have 202 keys. This is as uniform as possible.

Option C: $h(i) = (11 \cdot i^2) \mod 10$

Since $11 \equiv 1 \pmod{10}$, we have
$$
h(i) = (11 \cdot i^2) \mod 10 = (i^2) \mod 10.
$$
This is identical to Option A, and thus also uses only 6 buckets. The distribution is non-uniform.

Option D: $h(i) = (12 \cdot i^2) \mod 10$

Note that $12 \equiv 2 \pmod{10}$, so
$$
h(i) = (2 \cdot i^2) \mod 10.
$$
Compute for $i = 0$ to $9$:

\[
\begin{array}{|c|c|c|c|}
\hline
i & i^2 & 2i^2 & (2i^2) \mod 10 \\
\hline
0 & 0 & 0 & 0 \\
1 & 1 & 2 & 2 \\
2 & 4 & 8 & 8 \\
3 & 9 & 18 & 8 \\
4 & 16 & 32 & 2 \\
5 & 25 & 50 & 0 \\
6 & 36 & 72 & 2 \\
7 & 49 & 98 & 8 \\
8 & 64 & 128 & 8 \\
9 & 81 & 162 & 2 \\
\hline
\end{array}
\]

The residues are ${0, 2, 8}$ only 3 buckets are used. This is the least uniform of all options.

Conclusion

Only Option B produces a complete and balanced set of residues modulo $10$, resulting in a near-perfect uniform distribution across all buckets. All other options suffer from significant clustering due to algebraic properties of squaring or scalar multiplication modulo $10$.

$$
\boxed{\text{B. } h(i) = i^3 \mod 10}
$$

Answer 5

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