HackerRank ‘Halloween Sale’ Solution

Short Problem Definition:

You wish to buy video games from the famous online video game store Mist.

Usually, all games are sold at the same price, p dollars. However, they are planning to have the seasonal Halloween Sale next month in which you can buy games at a cheaper price. Specifically, the first game you buy during the sale will be sold at dollars, but every subsequent game you buy will be sold at exactly d dollars less than the cost of the previous one you bought. This will continue until the cost becomes less than or equal to m dollars, after which every game you buy will cost m dollars each.

Link

Halloween Sale

Complexity:

time complexity is O(1)

space complexity is O(1)

Execution:

The solution is based on the Arithmetic Progression. It makes it a bit more complex due to the floor m.

Another option is either a while loop or a recursion.

Solution:
// Complete the howManyGames function below.
int howManyGames(int p, int d, int m, int s) {
    int n=floor( (p-m)/d +1);
    if( (n*(2*p-(n-1)*d))/2 <= s)
    {
        return n + (s-(n*(2*p-(n-1)*d)/2))/m;
    }
    else
    {
        return floor(((-d-2*p)+sqrt((-2*p-d)*(-2*p-d)-(8*d*s)))/(-2*d));
    }
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin