Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 15 Dec, 2020

Easy

```
Let ‘x’ be a larger integer, ‘n’ be the size of the hash table, and ‘h(x) = x mod n’ be a hash function. Then in Quadratic Probing -:
1. If we find that the index h(x), is already mapped to some other integer in the hashtable, then we try for index (h(x) + 1 * 1) mod n.
2. If the index (h(x) + 1*1) mod n, is also already mapped to some other integer in the hashtable, then we try for index (h(x) + 2 * 2) mod n.
3. If the index (h(x) + 2*2) mod n, is also already mapped to some other integer in the hashtable, then we try for index ‘(h(x) + 3 * 3) mod n.
4. We repeat this process until an unmapped index is found in the hashtable or index values start repeating.
```

```
For Example -: Consider, array ‘keys’ = {50, 49, 76, 85, 92, 73, 18}, ‘n’ = 7 and the hash function h(x) = x mod 7. Then -:
1. h(50) = 50 mod 7 = 1, thus it will be mapped to index ‘1’ in the hashtable.
2. h(49) = 49 mod 7 = 0, thus it will be mapped to index ‘0’ in hashtable.
3. h(76) = 76 mod 7 = 6, thus it will be mapped to index ‘6’ in the hashtable.
4. h(85) = 85 mod 7 = 1, thus it should be mapped to index ‘1’ in the hashtable, but index ‘1’is already mapped with 50, so we try for index (h(85) + 1*1) mod 7 = ‘2’, as index ‘2’ is not mapped previously, thus it will be mapped to index ‘2’ in hashtable’.
5. h(92) = 92 mod 7 = 1, thus it should be mapped to index ‘1’ in the hashtable, but index ‘1’ is already mapped with 50, so we try for index (h(92) + 1*1) mod 7 = 2, but index ‘2’ is also occupied so we try for index (h(92) + 2*2) mod 7 = ‘5’, as index ‘5’ is not mapped previously, thus it will be mapped to index ‘5’ in hashtable
6. h(73) = 73 mod 7 = 3, thus it will be mapped to index ‘3’ in the hashtable.
7. h(18) = 18 mod 7 = 4, thus it will be mapped to index ‘4’ in the hashtable.
Thus the resultant array ‘hashTable’ should be {49, 50, 85, 73, 18, 92, 76}.
```

```
1. Consider ‘0’ based indexing.
2. Don’t print anything, just return the integer array ‘hashTable’.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.
The first line of each test case contains a positive integer ‘n’ representing the size of array ‘keys’.
The second line of the test case contains ‘n’ space-separated non-negative integers representing elements of the array ‘keys’.
```

```
For each test case, return an array ‘hashTable’ of size ‘n’ where the element at index ‘i’ is the element from the given array ‘keys’ that is mapped to that index or -1 is no element is mapped to that index.
Output for each query is printed in a new line.
```

```
1 <= T <= 50
1 <= n <= 100
0 <= keys[i] <= 10^9
Where ‘T’ is the total number of test cases, ‘n’ is the size of the given array ‘keys[i]’ is the elements of the given array.
Time limit: 1 sec
```

For every element in the array ‘keys’, we can observe that the index value will start repeating after ‘n’ probes. Thus we should try only ‘n’ time for one key.

- Make an integer array ‘hashTable’ of size ‘n’ and fill it completely with -1.
- Run a loop where ‘i’ ranges from 0 to n-1 and for each ‘i’ we try to find an index by which it should map in the hashtable. This can be done as follows.
- Calculate the hash value of ‘key[i]’ and store it in integer variable hash. I.e hash:= key[i] mod n.
- Run a loop where ‘j’ ranges from ‘0’ to ‘n’ and for each ‘j’ check whether the value at index (hash + j*j) mod n, in array ‘hashTable’ is -1 or not. If it is -1 then assign hashTable[i] := keys[i] and break the loop.

- Return this integer array ‘hashTable’.

Similar problems

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Maximum GCD

Hard

Posted: 8 Dec, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023