Last Updated: 1 Sep, 2021
Shops and Houses
Moderate
Asked in company
You have an ‘H’ number of friends who live in different ‘H’ houses. You are going shopping with them. To reduce the shopping time, you have to choose the shop closest to your friend’s house. You have two integer arrays, ‘SHOPS’ and ‘HOUSES’, representing the location of a shop and house in a city. For each house, you have to find the nearest shop location. If many shops are equidistant from a house, choose the shop with the smallest numerical location.
Example :
Give houses location, ‘HOUSES’ : {2, 4, 2}
Given shops location, ‘SHOPS’ : {5, 1, 2, 3}
The shops closest to each houses are : {2, 3, 2}
Input Format :
The first line of input contains an integer ‘T’, the number of test cases.
The first line of each test case contains a single integer ‘H’ representing the number of the houses.
The second line of each test case contains ‘H’ single space-separated integers representing the location of the houses.
The third line of each test case contains a single integer ‘S’ representing the number of the shops.
The fourth line of each test case contains ‘S’ single space-separated integers representing the location of the shops.
Output Format :
For each test case, print ‘H’ space separated integers denoting the closest shop to the ith house.
Output for each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= H <= 10^2
1 <= S <= 10^2
0 <= HOUSE[i], SHOP[i] <= 10^5
Where HOUSE[i], SHOP[i] represent the ith house and ith shop respectively.
Time Limit : 1 sec
Approaches
The basic idea is to traverse the ‘SHOP’ array for each house to find the shop nearest to a house.
Here is the algorithm :
- Create an array (say, ‘RES’) that will store the location of each shop and initialize it with a large number.
- Run a loop from 0 to ‘H’ (say, iterator ‘i’) to traverse the houses.
- Create a variable (say, ‘DIST’) that will store the distance between house and shop and initialize it with a large number.
- Run a loop from 0 to ‘S’ (say, iterator ‘j’) to traverse the shops.
- Check if ‘ABS(HOUSE[i] - SHOP[j])’ is smaller than ‘DIST’
- Update ‘DIST’ to ‘ABS(HOUSE[i] - SHOP[j])’.
- Update ‘RES[i]’ to ‘SHOP[j]’.
- Check if ‘ABS(HOUSE[i] - SHOP[j])’ is equal to ‘DIST’
- Update ‘DIST’ to ‘ABS(HOUSE[i] - SHOP[j])’.
- Update ‘RES[i]’ to a minimum of ‘RES[i]’ and ‘SHOP[j]’.
- Check if ‘ABS(HOUSE[i] - SHOP[j])’ is smaller than ‘DIST’
- Finally, return ‘RES’.
The idea is to sort the ‘SHOP’ array and then find the shop nearest to a house using binary search.
Here is the algorithm :
- Sort the ‘SHOP’ array.
- Create an array (say, ‘RES’) that will store the location of each shop and initialize it with a large number.
- Run a loop from 0 to ‘H’ (say, iterator ‘i’) to traverse the houses.
- Create a variable (say, ‘DIST’) that will store the distance between house and shop and initialize it with a large number.
- Create two variables (say, ‘LOW’ and ‘HIGH’) used for binary search and initialize them with 0 and ‘S’ - 1, respectively.
- Run a loop till ‘LOW’ is smaller than equal to ‘HIGH’.
- Create a variable (say, ‘MID’) and initialize it with an average of ‘LOW’ and ‘HIGH’.
- Check if ‘SHOP[MID]’ is equal to ‘HOUSE[i]’.
- Update ‘RES[i]’ to ‘SHOP[MID]’.
- Break out of the loop.
- Else, check if ‘ABS(HOUSE[i] - SHOP[MID])’ is equal to ‘DIST’
- Update ‘DIST’ to ‘ABS(HOUSE[i] - SHOP[MID])’.
- Update ‘RES[i]’ to a minimum of ‘RES[i]’ and ‘SHOP[MID]’.
- Check if ‘ABS(HOUSE[i] - SHOP[MID])’ is smaller than ‘DIST’
- Update ‘DIST’ to ‘ABS(HOUSE[i] - SHOP[MID])’.
- Update ‘RES[i]’ to ‘SHOP[MID]’.
- Check if ‘SHOP[MID]’ is smaller than ‘HOUSE[i]’.
- Update ‘LOW’ by ‘MID’ + 1.
- Else
- Update ‘HIGH’ by ‘MID’ - 1.
- Finally, return ‘RES’.
Similar problems