# Calculate the total items used, if for every x items used, you get one additional item to use

I am looking for a way to optimize this code so that it runs faster. I am trying to calculate the total items used, if for every x items used, you get one additional item to use.

This is the code I currently have. I get the correct result, but with a large amount of items, it is taking too long to calculate.

public static int TotalItems(int startingTotalItems, int newItemInterval)
{
int itemsUsed = 0;
int itemsUsedThisInterval = 0;
int totalItems = startingTotalItems;

while (totalItems > 0)
{
totalItems--;
itemsUsed++;
itemsUsedThisInterval++;
if (itemsUsedThisInterval == newItemInterval)
{
totalItems++;
itemsUsedThisInterval = 0;
}
}
return itemsUsed;
}

public static void Main(string[] args)
{
Console.WriteLine(TotalItems(3, 2));
}

Console output: 5

//-- psudo
// Use 2 items
// Now I have 1 item plus I get 1 new additional item, giving a total of 2 items
// Use 2 items
// Now I have 0 items but since I used another 2 items, I get 1 more new additional item
// Use 1
// I have used a total of 5 items - Thisis the result
//--

I think the issue is the use of the while loop. I would think that there would be an efficient algorithm I could apply for this but but, so far, I have not had any luck finding one.

What my boss is saying is "Your code took too long to calculate an answer. Analyze how your code behaves when the input increases in size and see if you can make it work faster."

• Does not make sense to me " if for every x items used, you get one additional item to use". To me 3,2 should get one extra item. By using totalItems++; you are double dipping on newItemInterval. Commented Oct 18, 2016 at 2:14

I managed to create another algorithm that produces the same results, this algorithm iteration seems to be more efficient so it will perform better.

Consider startingTotalItems as x and newItemInterval as y.

Using while loop:

public static int TotalItems(int x, int y)
{
int sum = 0;
while (x >= y)
{
int remainder = x % y;
int quotient = x / y;
sum += (x - remainder);
x = remainder +  quotient;
}
return sum + x;
}

Using recursive method:

public static int TotalItems(int x, int y)
{
if(x < y)
{
return x;
}
int remainder = x % y;
int quotient = x / y;
return x - remainder + TotalItems(remainder +  quotient, y);
}

How does it work?

Let's assume that x is the amount of items we are holding now.

For every x bigger than or equal to y we will add to the sum x without the remainder of x divided by y, let's consider that these are the items we've used during this turn.

Now we still have the remainder that we haven't used yet but we need to remember the we've got more items while using the previous items, the amount of items we've got is the quotient of x divided by y, so now x should be the quotient plus the remainder.

We will repeat this procedure until x is less than y in this case we know that we will not get any more items so all we have left to do is to add x to the sum, break the procedure and return the result.

• Your recursive method is exactly what I was looking for. Thanks for the help. Commented Oct 18, 2016 at 11:54
• Also, thanks for explaining how it works. I really appreciate it. Commented Oct 18, 2016 at 11:57
• I'm glad it helped you, just for curiosity did you do any times measurements to compare the performance of your old algorithm and this one? Commented Oct 18, 2016 at 12:06
• Very well done. Try calling either function with y = 0 or 1, however. Commented Oct 18, 2016 at 13:46

Yes, your while loop is suboptimal leading to increased loops and increased time for larger values.

The problem can be solved mathematically. Consider this:

$$s = \mathtt{startingTotalItems}\\ n = \mathtt{newItemInterval}\\$$ $$f(s, n) = \begin{cases} \emptyset, &\text{when n\lt0}\\ s, &\text{when n=0}\\ \infty, &\text{when n=1}\\ s + f(s\ \mathbf{div}\ n + s\ \mathbf{rem}\ n, n), &\text{when n\gt1}\\ \end{cases}$$

Using a little algebra the last equation can be factored into a single operation.

• This looks like what I want but I feel I lack the math background to properly translate your equation. Given a startingTotalItems of 3 and a newItemInterval of 2, I believe your equation says 3 + (3 / 2) + ( 3 % 2) which gives the correct value of 5 in this case, but what does the comma followed by n (newItemInterval) mean? Commented Oct 18, 2016 at 4:28
• @DaveAdler The mathematic function denotes recursion -- calling the function again with s set to s \ n + s % n and n set to n. This could be translated to code literally as a recursive call, or refactored into a more efficient loop as @SomeUser demonstrated, or a single expression. The single expression would be the most efficient with O(1). Don't forget the handle the three other conditions for n ≤ 1. Commented Oct 18, 2016 at 5:02
• There is a mistake in your algorithm or I did not understand it fully , the recursive call will never reach to it's end, because n will never be changed. Besides that try to use s=17 and n=6, you will not get the desired result of 20 because you will add 17+7+2... Commented Oct 18, 2016 at 7:22
• Eventually f(s, n) will result in 0. Recursion would stop then. I think you're right about my equation being incorrect. I'll try to fix it. Commented Oct 18, 2016 at 7:50
• @psaxton please refer my edit. Commented Oct 18, 2016 at 8:21