GFG App
Open App Browser
Continue

# GATE | GATE-CS-2015 (Set 2) | Question 65

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) = (12 ∗ i) mod 10

(B)

h(i) = (11 ∗ i2) mod 10

(C)

h(i) =i3 mod 10

(D)

h(i) =i2 mod 10

Explanation:

Since mod 10 is used, the last digit matters.

If you do cube all numbers from 0 to 9, you get following

```Number    Cube    Last Digit in Cube
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  ```

Therefore all numbers from 0 to 2020 are equally divided in 10 buckets. If we make a table for square, we don\’t get equal distribution. In the following table. 1, 4, 6 and 9 are repeated, so these buckets would have more entries and buckets 2, 3, 7 and 8 would be empty.

```Number   Square     Last Digit in Square
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  ```

Alternative approach –
Using 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.
Option (B) is correct.

Quiz of this Question
Please comment below if you find anything wrong in the above post

My Personal Notes arrow_drop_up
{"ft_lang_label":"__label__en","ft_lang_prob":0.7672749,"math_prob":0.97772217,"size":1281,"snap":"2023-14-2023-23","text_gpt3_token_len":517,"char_repetition_ratio":0.110415034,"word_repetition_ratio":0.029962547,"special_character_ratio":0.43091336,"punctuation_ratio":0.15512465,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96321565,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-03T21:05:03Z\",\"WARC-Record-ID\":\"<urn:uuid:45134062-12fc-4837-9349-1aa45c967669>\",\"Content-Length\":\"231371\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:09dbb0cc-479d-44d1-b104-2f410417addd>\",\"WARC-Concurrent-To\":\"<urn:uuid:67806c14-8619-464a-9636-2d51a920258c>\",\"WARC-IP-Address\":\"44.228.100.190\",\"WARC-Target-URI\":\"https://origin.geeksforgeeks.org/gate-gate-cs-2015-set-2-question-43/\",\"WARC-Payload-Digest\":\"sha1:B6TSTUVUA4REKXVVKF37XNFEJYBAWJPU\",\"WARC-Block-Digest\":\"sha1:ININZGLMCYJHKHYZI2V74POEKH32GTQC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224649343.34_warc_CC-MAIN-20230603201228-20230603231228-00633.warc.gz\"}"}