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

Question

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 
// Start with 3 items
// 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."

Answer 1

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.

Answer 2

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.