I can't stop thinking in this coding problem

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

Top comments (5)

Tyler V. (he/him) • Apr 5 '19

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 3 in 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:

Record the length of the perf array
Sort the array of preferred numbers largest to smallest
Loop through n from largest to smallest - This will account for the fact that larger numbers will factor into less numbers.
Check if n is a factor for each number in the array (largest to smallest)
If n is a factor, pop the value from the array (to indicate that driver has a car now)
Once you either run out of cars or run out of drivers, subtract the length of the remaining drivers array from the initial length of the array.

Unless I'm missing a corner case somewhere, this should return the correct value.

protium • Apr 5 '19

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!

Tyler V. (he/him) • Apr 5 '19

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