0

I need to solve a test question that asks to count how many apples can be eaten in total when X apples are given as a start amount, Y apples are eaten every time, and 1 apple is added every time apples are eaten.

My current solution uses a recursive function and therefore would cause an infinite loop if Y is smaller than X or if given X is way large.

public class Apples
{
    // Counts iterations. If we eat less than we add new every, it'll loop infinetely!
    private static int _recursions;

    private static int _applesRemaining;
    private static int _applesEaten;


    public static int CountApples(int startingAmount, int newEvery)
    {
        if (newEvery > startingAmount) newEvery = startingAmount;
        Console.WriteLine("startingAmount: " + startingAmount + ", newEvery: " + newEvery);

        _applesRemaining = startingAmount;

        /* Eat 'newEvery' amount */
        _applesRemaining -= newEvery;
        _applesEaten += newEvery;

        Console.WriteLine("Eat: " + newEvery + ", remaining: " + _applesRemaining);

        /* Get one additional candy */
        _applesRemaining += 1;
        Console.WriteLine("Added 1.");

        if (_applesRemaining > 1 && _recursions++ < 1000)
        {
            CountApples(_applesRemaining, newEvery);
        }
        else
        {
            if (_recursions > 1000) Console.WriteLine("ABORTED!");

            /* Eat the one we've just added last. */
            _applesEaten += 1;
        }

        return _applesEaten;
    }


    public static void Main(string[] args)
    {
        Console.WriteLine(CountApples(10, 2) + "\n");
    }
}

How can I make this more efficient? There's probably a more elegant way to do this but I can't figure it out.

EDIT: Original test question text:

/**
 * You are given startingAmount of Apples. Whenever you eat a certain number of
 * apples (newEvery), you get an additional apple.
 *
 * What is the maximum number of apples you can eat?
 *
 * For example, if startingAmount equals 3 and newEvery equals 2, you can eat 5 apples in total:
 * 
 * Eat 2. Get 1. Remaining 2.
 * Eat 2. Get 1. Remaining 1.
 * Eat 1.
 */
Improve this question
12
  • 1
    Y apples are eating every time. Can you explain about this? It's funny to know that apples are eating. Do yo mean eaten? Commented Jul 16, 2018 at 9:54
  • This sounds like it simplifies into a linear equation, but either way there's no need to use recursion. Commented Jul 16, 2018 at 9:55
  • @david that was a typo. corrected. Commented Jul 16, 2018 at 9:55
  • What happens when there are 3 apples to start with, and 5 apples are eaten each time? Commented Jul 16, 2018 at 9:57
  • 2
    Having seen your update I want to try to clarify things: Y apples are not eaten every time. Apples are eaten one at a time and every time you reach a multiple of Y you add an extra apple. This is absolutely unambiguously clear in its specification. Commented Jul 16, 2018 at 10:40

5 Answers 5

Reset to default
3

Not sure if you are restricted in the answer but with some maths you can come up with the following method:

public int CheatEatenApples(int startingApples, int newEvery)
{
    var firstGuess = (double)startingApples*newEvery/(newEvery-1);

    if (firstGuess%1==0) // Checks if firstGuess is a whole number
    {
        return (int)firstGuess-1;
    }
    else
    {
        return (int)firstGuess;
    }
}

The first guess is calculated using the fact that we keep getting new apples so for every newEvery apples we've eaten one of them was free! Of course this actually breaks down if the first guess is a whole number. This would require the free apple to have been given in order to allow us to eat it. Confusing so lets look at an example.

If we have 3 apples and we get a new apple every two then our first guess is 6 apples. However that's three free apples and we'd only get the third one after we've eaten 6 which relies on three free ones! So in this case we need to take one off. The rest of the time we can just round down to remove the fractional part which represents how close we are to a free apple.

And this just goes to show that the maths you learn at school can be used in the real world. The above is a few simple calculations and is probably going to be faster than most iterative/recursive methods of calculating this.

Additional note: It was pointed out in a now deleted comment that this could be better done using integer arithmetic for the firstGuess calculation. This would save needing to cast back to int for the return value. The reason it is written as it is currently is partly because it is the way I was thinking about it when writing it and partly because while I was iterating for the right answer I was viewing that decimal part while debugging (to confirm it was only when firstGuess was whole that I needed to do something special).

If you did change to integer maths instead then the if condition would need to be changed (since it would no longer work as is) and you would then end up with Sefe's answer.

Final Note:

If you did want to do an iterative technique then the following method matches the specification:

public int CalculateEatenApples(int startingApples, int newEvery)
{
    int applesEaten = 0;
    int apples = startingApples;
    while (apples>0)
    {
        applesEaten++;
        apples--;
        if (applesEaten%newEvery==0)
        {
            apples++;
        }
    }
    return applesEaten;
}

Its pretty straightforward. while you have apples it increases the count of ones you've eaten and decreases those you have left. Then if the number you have eaten is a multiple of newEvery then it adds an extra one.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I didn't know you could do double%1 to do that check. Nice.
@MineR: I was not 100% sure the best way to do the check so found the recommendations in stackoverflow.com/questions/2751593/…
@PaulF: I think you are probably right. The method above was written as that as a combination of how I was thinking about it in my head and because while iterating and testing I was looking at the decimal parts of that. I'm going to leave it as it is for now. Partly because changing to integer arithmetic would mean changing my if condition and what I'd have to change it to would make it basically identical to Sefe's answer. :) At least now there are two slightly different versions to choose between. :)
I did see the subtle difference in the if statement afterwards & removed my comment.
@PaulF: I think it was absolutely a good comment and worth keeping to the extent that now you've deleted it I will go and add a note to my answer instead. :)
2

Recursion for this problem seems like overkill so I'd suggest an alternative mathematical approach.

Lets start with the fact that we'll always eat at least X apples. The real question is how much apples in total will have been added after everything gets eaten.

Say that ni will be the number of apples remaining after i "eatings". Then:

n0 = X
n1 = X - Y + 1
n2 = X - 2Y + 2
...
ni = X - i(Y - 1)

Solving for ni = 0 will give us i - the number of "eatings" required to eat everything:

ni = 0 = X - i(Y - 1) => i = X / (Y - 1)

Now we know how many times we'll eat, so the total number of apples that are going to be eaten is the original X plus the number of times Y apples get eaten (since every time we get an extra apple when doing so):

tot = X + roundDown(i) = X * roundDown(X / (Y - 1))

We round down the result since setting ni = 0 captures a partial number of "eatings" that then result in partial apples.

Example:

X = 7, Y = 3 => tot = 7 + roundDown(7 / (3 - 1)) = 7 + roundDown(3.5) = 10
starting with 7:
0 eaten, 7 remain
3 eaten, 1 gained, 5 remain
3 eaten, 1 gained, 3 remain
3 eaten, 1 gained, 1 remains
1 eaten, nothing gained, nothing remains
--
10 eaten in total
Improve this answer

Comments

2

If you only want to count the apples eaten without tracking the progress you need no recursion and no loop. You can simply calculate the result with linear O(1) code:

int result = apples + apples / (eatenPerRound - 1);
if ((apples % (eatenPerRound - 1)) <= 1) {
    result--;
}
Console.WriteLine($"Total number of {result} apples eaten.");
Improve this answer

9 Comments

I'm quite sceptic about this approach
@Rafalon Sceptic about whether the result answers the question correctly? The question is "What is the maximum number of apples you can eat?". This question is answered.
Note this doesn't give the result he requires for 3 starting, 2 eaten per round... Should give 5, but gives 6.
If you can change it to make it work, it deserves an upvote for being fastest. :)
@Sefe MineR's comment is exactly why I was sceptic about this approach
|
1

Here is a running example of how I understood your problem:

using System.IO;
using System;

class Program
{
    static void Main()
    {
        Console.WriteLine(GetNumberOfApplesEaten(100,5));
    }

    public static int GetNumberOfApplesEaten(int X, int Y)
    {
        int result = 0;

        // while we can eat 'Y' apples
        while(X >= Y)
        {
            // we eat & count those apples
            result += Y;
            X -= Y;
            // we add an extra apple
            X++;
        }
        // we eat what's left
        result += X;

        return result;
    }
}

Edit

I changed X > Y to X >= Y so it matches your specs.

Check javascript equivalent:

function getNumberOfApplesEaten(X,Y) {
    var result = 0;

    // while we can eat 'Y' apples
    while(X >= Y) {
        // we eat & count those apples
        result += Y;
        X -= Y;
        // we add an extra apple
        X++;
    }
    // we eat what's left
    result += X;

    return result;
}

console.log(getNumberOfApplesEaten(3,2))

Improve this answer

2 Comments

This works for me, thanks a lot! I added a check in case Y is 1 which will result in an infinite loop.
@BadmintonCat yes, you should definitely check that X > 0 and Y > 1
0

I don't have a C# toolchain at hand, so the example below is in Python Community edits have made the example C#! Magic!

As said in the comments, this is an iterative problem, not a recursive one.

var apples = 100;
var eaten = 0;
var eatPerRound = 5;
var gainPerRound = 1;

while(apples > 0)
{
    apples -= eatPerRound;
    eaten += eatPerRound;
    apples += gainPerRound;
    Console.WriteLine($"Round {round}: {eaten} apples eaten, {apples} left");
}

Round 1: 5 apples eaten, 96 left
Round 2: 10 apples eaten, 92 left
Round 3: 15 apples eaten, 88 left
Round 4: 20 apples eaten, 84 left
Round 5: 25 apples eaten, 80 left
Round 6: 30 apples eaten, 76 left
Round 7: 35 apples eaten, 72 left
Round 8: 40 apples eaten, 68 left
Round 9: 45 apples eaten, 64 left
Round 10: 50 apples eaten, 60 left
Round 11: 55 apples eaten, 56 left
Round 12: 60 apples eaten, 52 left
Round 13: 65 apples eaten, 48 left
Round 14: 70 apples eaten, 44 left
Round 15: 75 apples eaten, 40 left
Round 16: 80 apples eaten, 36 left
Round 17: 85 apples eaten, 32 left
Round 18: 90 apples eaten, 28 left
Round 19: 95 apples eaten, 24 left
Round 20: 100 apples eaten, 20 left
Round 21: 105 apples eaten, 16 left
Round 22: 110 apples eaten, 12 left
Round 23: 115 apples eaten, 8 left
Round 24: 120 apples eaten, 4 left
Round 25: 125 apples eaten, 0 left
Improve this answer

7 Comments

This is an online C# compiler I frequently use
That doesn't quite add up. Given X is 3 and Y is 2 it should result in 5 (eat 2, add 1, eat 2, add 1, eat 1), but this code returns 6.
@BadmintonCat You have 3, you go to eat and now you have 4, you eat 2, and have 2 left, you go to eat and you have 3, you eat 2 and have 1 left, you go to eat and have 2, you eat and have 0 left. Total is 6.
@BadmintonCat the order in which the extra apple is added is important.
@MineR Ok, but that's not how the test question gives an example (it does as in my previous comment).
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.