Changing Summation Limits: A Computational Solution To A Programming Interview Question

I recently came across a coding interview question that asks the programmer to distribute some number of items, to a row of n people in the following way:

The Interview Question

We start our first turn by giving 1 item to the first person, 2 items to the second person, and so on until we give n items to the last person.
Then, we go back to the start of the row and begin our second turn, giving n+1 items to the first person, n+2 items to the second person, and so on until we give 2n items to the last person.
This process repeats (with us giving more items each time, and moving to the start of the row after we reach the end) until we cannot give the adequate amount of items to every person for a given turn.
Return an array that contains the number of items that are distributed for each turn in O(turn). (This means that it will only take twice as long to give out items for a row of 20 people than a row of 10 people even though there are around 4 times as many items to give out)

The Solution

The best approach to this problem is to solve it computationally. Before we dive into the mathematics behind the solution, let’s first define our variables.
j = the current turn
n = the number of people
i = the position of a given person in the row where { i ϵ ℤ | 1 ≤ i ≤ n }

For a given j, we know that n is constant and that i will increase by 1 each time we move on to the next person. The number of items given to the ith person is entirely dependent on j, n and i with the relationship of items=jn+i. In English, the number of items given to the ith person on the jth turn is equal to the current turn multiplied by the number of people in the row plus the position of the given person in the row. Expressing this as a mathematical expression gives:

This, however, does not seem very helpful at first. It looks as though we took a simple problem and turned it into something only Bernhard Reimann, himself, could solve. That is of course until we recognize that this summation can be manipulated into the famous form of a summation of the first n positive integers.

As a quick review for those of you who are not familiar with finding the sum of the first n positive integers, here is the solution to the equation:

If you would like to learn more about the proof behind this solution, check out this link here: https://brilliant.org/wiki/sum-of-n-n2-or-n3/

Note that jn appears in the lower limit and the upper limit of our summation. Therefore, the lower limit and the upper limit only differ by n, so we can legally remove jn from the bounds and place it inside of the summation. In order to have our summation in the desired form, we need to pull jn out of the summation (this is legal since both are constant for a given turn). When we pull jn out of the summation, we multiply by an extra n in order to account for the fact that the jn will no longer be added n times when it is outside of the summation, thus giving jn² summing together with the summation. This means that:

We now have our summation in the desired form, so we can finally substitute out our summation and set the resulting equation equal to the number of items that are given during turn j.

In review, we have found a mathematical expression (5) that is easily computable, and that also represents the number of items that are given during turn j by changing summation limits and manipulating a summation to match the form of a more digestible summation.

The Code

Now that we have the mathematics out of the way, let’s code up the solution to the question in Python.

In the code above, we define a function on line 1 named distrubuteItems that takes two parameters, the number of items to give, and the number of people in the row, and it returns a list that contains the number of items given for each full turn (this means that it excludes the final turn if there are not enough items to distribute to everyone).
On line 2 we define the itemsPerTurn list that we will populate with the number of items given for each turn and return it on line 10.
On line 3 we define our j variable so that we can keep track of which turn we are on.
Line 4 computes the number of items required for turn 0.
On line 5, we enter a while loop with the condition that the remaining number of items must be greater than or equal to the number of items required for turn j.
Line 6 decrements the number of remaining items by the number of items required for the given turn j.
Line 7 finally appends the number of items required for the given j to the itemsPerTurn list before incrementing j by 1 on line 8.
Line 9 then computes the number of items required for turn j which is the equation that we worked so hard for.
Finally, on line 10, we return our itemsPerTurn list populated with the number of items given for each full turn.

Thanks for reading. Do you have some questions? Let me know what in the comment section.

Share the article, so other developers and mathematicians can read it too.