It seemed an easy problem. I even took care of edge cases I think. I don’t know why I’m getting WA. Will the submissions be made public?
Do you have the link to the problem and your attempted solution?
You are not considering the probability of overflow in lcm. I also got a wrong answer verdict for the same condition.
My accepted solution link is Solution Link
What is the LCM overflow condition? Can you explain a bit?
Your solution is giving WA on corner case.
Here it is :https://ideone.com/mwfrVA
The correct answer is +1.
let we have found lcm upto index i - 1. Then for our current index i , lcm would be lcm = (lcm*arr[i]) / (gcd(arr[i] , lcm))
Here you are multiplying two possibly large numbers which could extend upto number more than 10^9. These would lead to overflow since long long is also not capable of holding such large numbers. So I have kept a condition which would not let number to exceed my upper bound.
The condition for the same is if (R < (lcm*arr[i]) . gcd(lcm , arr[i])) then break my loop. The further simplification can be seen in the code which I have linked in my answer.
Hope this helps.
sorry, your link is private(it says “forbidden”). could you please make a public link or tell me the testcase here?
it was not what you said but it had to do with the lcm! I use ceil function in the code and when lcm got very very large, ceil(1/lcm), which i expected to give 1, gave 0. thanks!
got AC! thanks.
It is working now. Sorry for inconvenience.
If anyone’s interested in C++ solution - Link
Thanks. By the way, could you please tell how did you find this case? Did you have access to the cases, did you generate cases specifically for this problem or is there some tool I am unaware of?
I just tried to generate the worst case. I just needed to find when n and m both are zero. In such cases, your code would have been failed. And I don’t have access to test cases. I generated this specifically for this question after seeing your post.