I had this problem during a live session:
There is going to be a car race. The cars are numbered from 1 to n. Drivers will only get a car if the number of the car is a factor of their preferred number. Find the maximum number of participants.
E.g. n = 3, prefsNumbers = [9, 1, 5], output: 2
1 <= n <= 1000; 1 <= prefsNumbers[i]
I had 2 approaches:
- Build a matrix n x m finding a driver for each car. Every row represents a car and every cell [i,j] is true if the car number i is factor of the participan j preferred number. Then For each row find whether there is at least one driver. If so add one to the total number of participants. E.g
|9 1 5 --------- 1 |1 1 1 2 |0 0 0 3 |1 0 0 Cars 1 and 3 have at least one possible driver. The output is 2
- Sort the prefsNumbers by the number of factors of each preferred number, thus I will find a car first for the numbers that have few chances of getting one, starting with prime numbers
Both approaches didn't pass all the test cases. What am I missing here?
Top comments (5)
I don't think returning the row of the matrix with the most
1's is what you want to do, since that would return
3in your example, but the answer is 2. The driver with pref=9 can get in car #3, but then the drivers with pref 5 and 1 are left fighting for car #1 (Can't have 2 drivers in 1 car!).
The way that I would approach this is as follows:
Unless I'm missing a corner case somewhere, this should return the correct value.
Sorry, I will correct the description. I meant for each row (car) that has at least 1 driver I add one to the number of participants to return. So I only care about the car having at least one driver. Also I check that the number of participants is not greater than the number of cars.
Your solution sounds great.
Thanks for your answer!
I see what you mean.
If you do it that way, you aren't necessarily catching each driver once.
For example, if you have 4 cars and driver's with preferences of [8,7,5,1] the correct answer is 2, but because 8 is okay with cars 1,2 and 4, that method would return 3
You are right! I wasn't able some how to find the issue with that solution so I decided to post it here so I could sleep tonight haha. Thanks!
Haven't checked this thoroughly but this might be a solution:
For each preferred number
Find number of elements in set.