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

Last Updated: 20 Dec, 2020

Easy

```
1. Consider ‘0’ based indexing.
```

```
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a positive integer ‘N’ representing the size of array KEYS.
The second line of each test case contains ‘N’ space-separated non-negative integers representing elements of the array KEYS.
```

```
For each test case, return an array 'HASH_TABLE’ of size ‘N’ where HASH_TABLE[ i ] is the element from the given array KEYS which is mapped to the index i.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 500
0 <= KEYS[ i ] <= 10^9
Time limit: 1 sec
```

The approach is pretty simple. We just need to find the mapping index and if it is occupied, we need to search for the next available index.

- Create an array HASH_TABLE
**of size N**. - Initialise every value of HASH_TABLE as -1.
**Loop for each KEY:**- Initialize
**HASH = KEY % N** - If HASH_TABLE[ HASH ] is already occupied, we perform:
- while(HASH_TABLE[ HASH ] != -1):
**HASH = ( HASH + 1 ) % N, iterating for valid hash index.**

- while(HASH_TABLE[ HASH ] != -1):
- Update HASH_TABLE[ HASH ] with KEY.

- Initialize
- Return HASH_TABLE

- Initialise HASH_TABLE
**= { -1, -1, -1 }** - For 91,
**H(91) = 91 mod 3 i.e. 1.**- As index 1 is free, HASH_TABLE
**becomes { -1, 91, -1 }.**

- As index 1 is free, HASH_TABLE
- For 28,
**H(28) = 28 mod 3 i.e. 1**.- As index 1 is already occupied, we will move to while loop:
- We use index 2, which is free, HASH_TABLE
**becomes { -1, 91, 28 }**

- We use index 2, which is free, HASH_TABLE

- As index 1 is already occupied, we will move to while loop:
- For 46,
**H(46) = 46 mod 3 i.e. 1**.- As index 1 is occupied, we move to while loop:
- HASH = (1 + 1) mod 3 i.e. 2. As index 2 is occupied, loop continues.
- HASH = (2 + 1) mod 3 i.e. 0. Index 0 is free, thus, we will use index 0.

The final HASH_TABLE becomes { 46, 91, 28 }

Similar problems

Longest Subarray With Zero Sum

Moderate

Posted: 3 Nov, 2022

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

Negative To The End

Easy

Posted: 16 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023