DEV Community

Discussion on: I can't stop thinking in this coding problem

Collapse
terabytetiger profile image
Tyler V. (he/him)

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:

  1. Record the length of the perf array
  2. Sort the array of preferred numbers largest to smallest
  3. Loop through n from largest to smallest - This will account for the fact that larger numbers will factor into less numbers.
  4. Check if n is a factor for each number in the array (largest to smallest)
  5. If n is a factor, pop the value from the array (to indicate that driver has a car now)
  6. 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.

Collapse
protium profile image
protium Author

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!

Collapse
terabytetiger profile image
Tyler V. (he/him)

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

Thread Thread
protium profile image
protium Author

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!