GATE CS 2026 Set 2 Q20 — Searching, Sorting, Hashing

To find the length of the longest chain, we compute the hash value $h(k) = k \bmod 9$ for each given key and group them by their hash index (from $0$ to $8$):

• Index 0: None
• Index 1: $28 \bmod 9 = 1$, $19 \bmod 9 = 1$, $10 \bmod 9 = 1$   $\rightarrow$   Keys: $\{28, 19, 10\}$ (Chain length = $3$)
• Index 2: None
• Index 3: $12 \bmod 9 = 3$   $\rightarrow$   Keys: $\{12\}$ (Chain length = $1$)
• Index 4: None
• Index 5: $5 \bmod 9 = 5$   $\rightarrow$   Keys: $\{5\}$ (Chain length = $1$)
• Index 6: $15 \bmod 9 = 6$, $33 \bmod 9 = 6$   $\rightarrow$   Keys: $\{15, 33\}$ (Chain length = $2$)
• Index 7: None
• Index 8: $26 \bmod 9 = 8$, $17 \bmod 9 = 8$   $\rightarrow$   Keys: $\{26, 17\}$ (Chain length = $2$)

The longest chain occurs at index $1$ with $3$ keys. Thus, the length of the longest chain is $3$.