# Halloween Sale

# Halloween Sale

adityangt + 1 comment A simple approach

static int howManyGames(int p, int d, int m, int s) { int count = 0; while(s>=p){ count++; s -=p; p = Math.max(p-d,m); } return count; }

artem_ua + 0 comments Yeah! A little variation:

`int count = 0; while(s >= 0) { s -= Math.Max(p, m); p -= d; count++; } return Math.Max(0, count - 1);`

mnaydin + 3 comments My implementation in C with O(1) running time complexity. It does not use any loop.

#include <stdio.h> #include <math.h> int main (void) { int p, d, m, s; int n, t; scanf("%d%d%d%d", &p, &d, &m, &s); if (s < p) { n = 0; } else { n = 1 + (p - m) / d; t = n * (2 * p - (n - 1) * d) / 2; if (s >= t) { n += (s - t) / m; } else { int b = 2 * p + d; n = (b - sqrt(b * b - 8 * d * s)) / (2 * d); } } printf("%d\n", n); }

rasik210 + 1 comment Very nice! The whole solution worked for me in C# as well except for one test case:

Input: 100 19 1 180 Expected output : 1

I handled this edge case by adding an additional if condition:

`if (sumOfMoney < priceOfGame) Console.WriteLine(0); else if (sumOfMoney < priceOfGame * 2) Console.WriteLine(1); else { //A.P. series based processing }`

mnaydin + 1 comment The condition (sumOfMoney < priceOfGame * 2) is not an edge case, and my C program above deals with the input

100 19 1 180

correctly (in the last else statement) by solving a quadratic equation obtained from arithmetic progression formula. It prints out 1, which is the correct solution.

Moreover, your handling of "edge case" is incorrect. Assume an input

100 20 1 180

with correct output

2

Your program would print out

1

which is wrong.

rasik210 + 1 comment You were right. Initially, when I converted your C code into C# code, I had to do few castings in the expression to overcome compilation issues. The compilation issue was coming in nested else block where you are performing square root operation. Those casting issues were related to int to float conversion. With the new castings applied when I ran you code then this particular test case failed which I've mentioned in my first comment. So, I applied this additional check to pass all test cases. I was able to fix it now. I changed the expression to apply casting on the whole R.H.S. expression instead:

n = (int)((b - Math.Sqrt(b * b - 8 * d * s)) / (2 * d));

Your entire solution is correct as is. Thank you so much for providing this feedback.

mnaydin + 0 comments I must note that my program may not be correct for larger numeric limits due to integer overflows, round-off errors, precision loss during conversion from float to int that you mentioned in your post. But within numeric limits given in the problem constraints, I believe, it should be correct though I didn't test it extensively.

petia_davidova + 0 comments [deleted]

loudking + 5 comments Hi may I ask if anybody getting this error while passing tests? I passed all tests except number 7. Input is '99 3 1 5555', expected output is '3905'. My output is also '3905' but HackerRank keeps complaining it is wrong ...

chakri_learner + 0 comments In my case 3 test cases are failing. checked TC number 11 : 1 1 1 9981 ; expected output is 9981 and my o/p is also the same but still it is failed.

tushartyagi8750 + 0 comments same problem with me bro

aniketnath283 + 0 comments simpliest solution for any language https://www.hackerrank.com/challenges/halloween-sale/forum/comments/484670

jainanupam + 0 comments Same here! Though the same logic and solution works fine in C, the same is failing in Python. Strange! @TeamHackerrank, please have a look.

mfguven + 0 comments [deleted]

str1kebeam + 5 comments def howManyGames(p, d, m, s): games = 0 while s >= 0: s -= p p = max(p - d, m) games += 1 return games - 1

rasik210 + 4 comments This is an AP series problem untill the remaining money becomes less than or equal to minimum cost. So, it should be solvable in O(1) time complexity without any loops.

harikaprathi + 0 comments How without any loops? I thought their has to be a loop to check till the total sum is not greater than the s amount in the wallet.

amdokamal + 1 comment That is true! Solved in O(1), but I found only a complex solution.

jlokhande46 + 1 comment Access denied

amdokamal + 0 comments The sequence forms arithmetic progression, you need just take into account 'm'. To find the sum of the first n terms in an Arithmetic sequence, you need to solve Quadratic equation.

blackjar72 + 0 comments I tried doing this, but while its easy given that you always reach at least the one step before hitting minimum before running out of money, I wan't sure how to handle cases where you didn't reach that cut off. I'm curious a full O(n)=1 solution and try to understand it.

alsomailbox_hr + 0 comments Yes, some maths (combinatorics, quadratic equation) and no loops.

https://www.hackerrank.com/challenges/halloween-sale/submissions/code/96765423

codebloodedsp + 0 comments it is not running for all test cases?

rounak077 + 2 comments nice small code, mine is very big but passes all test case

a = [p] for i in range(1,1000000): if a[i-1]-d > m: a.append(a[i-1]-d) else: a.append(m) sum = 0 # print(a) count = 0 for i in range(len(a)): if sum <= s: sum += a[i] count += 1 print (count-1) return count-1

harikaprathi + 1 comment This is also

rounak077 + 0 comments thanks, i just started to learn python. in my view it very simple as compare to JAVA

kowshik700 + 1 comment I use to code just like you when i started python...Predict the maximum number that can occur in test case and code for it.....I would suggest you to look at the constraints that will be given in the problem statement.....It greatly reduces your computing time...!! Happy coding..!

jlokhande46 + 0 comments Thank you for your suggestion :)

mayank612512 + 0 comments if you put condition in while loop (s >= m) instead of (s >=0), then your loop will run 1 times less and also then you can return (games) instead of (games - 1).

mudroljub + 0 comments Minor fix:

def howManyGames(p, d, m, s): games = 0 while s >= p: s -= p p = max(p - d, m) games += 1 return games

hidi_tibi + 2 comments No need to use loop here, because in can be calculated constant time, it is an arithmetic series.

victorz + 0 comments It's a bit tricky, but I've solved it that way. https://www.hackerrank.com/challenges/halloween-sale/submissions/code/67937852

Also note that it technically isn't "constant time", as operations like addition, subtraction, multiplication, and square root need more than "constant time" to compute.

amdokamal + 0 comments That is true! Solved in O(1), but I found only a complex solution.

Sort 218 Discussions, By:

Please Login in order to post a comment