I encountered a fun coding challenge while programming today.
Suppose you are teaching a class and you brought with yourself a bag of candy to hand out to your students. You want to hand out every piece of candy, but do it in a way that disperses the candy provided to each student as evenly as possible. No student should have more than 1 extra piece of candy than any other student. Exactly which students get the extra pieces of candy does not matter.
Task: Write a function that takes N students and M pieces of candy, where M > N, and returns an array of length N showing the amount candy given to each student.
Followup Task: Generate this array in O(N) time, where N is the number of students (NOT the amount of candy!)
spoilers maybe?
@wallhackio Why is this not just M mod N entries of ceil(M/N) and the remaining entries of floor(M/N)?
re: spoilers maybe?
@aschmitz yeah thats what it is
re: spoilers maybe?
@wallhackio It's funny, you can of course come up with a much faster setup function and a query function to return the amount of candy per consumer, but the asymptotic runtime gets wonky if you stare it down too hard or make it too asymptotic.
re: spoilers maybe?
@wallhackio Modular arithmetic on very large numbers has asymptotic bounds I don't remember, and which change depending on the scale of the numbers.