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?