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
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:
1
2
3
4
5
6
7
8
9
10
11
12
|
// 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)); } } |