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?

Edited: the description of the first solution was wrong