# 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

**people in the following way:**

*n*# The Interview Question

We start our first

by giving 1 item to the first person, 2 items to the second person, and so on until we giveturnitems to the last person.n

Then, we go back to the start of the row and begin our second, givingturnitems to the first person,n+1items to the second person, and so on until we given+2items to the last person.2n

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 ofthat are distributed for eachitemsturninO(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 turnn = the number of peoplei = the position of a given person in the row where { i ϵ ℤ | 1 ≤ i ≤ n }*

For a given ** j**, we know that

**is constant and that**

*n***will increase by 1 each time we move on to the next person. The number of items given to the**

*i***th person is entirely dependent on**

*i***,**

*j***and**

*n***with the relationship of**

*i***. In English, the number of items given to the**

*items=jn+i***th person on the**

*i***th 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:**

*j*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:

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

**, so we can legally remove**

*n***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**

*jn***in order to account for the fact that the**

*n***will no longer be added**

*jn***times when it is outside of the summation, thus giving**

*n***summing together with the summation. This means that:**

*jn²*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.