Getting runtime error in CHMOD

Problem : https://www.codechef.com/LRNDSA05/problems/CHMOD
my solution : https://www.codechef.com/viewsolution/36597353

What I did in my code (please check, my logic is correct or not) -
we have array of n numbers :
let, array is :arr[] = [1 2 3 4 5] // (size = 5)
I declared a new array"mul" with size (n + 1) and take mul[0] = 1
then iterate through arr and update mul[i] with (mul[i - 1] * arr[i]) % M, which gives mul as -
mul = [1, 1, 2, 6, 24, 120] // here, M = 1e9
Here, mul[i] gives multiplication of array till ‘i’ mod M
Is this approach is correct? If correct then where it gives runtime error.

I think this is a valid test input:

10
10 10 10 10 10 10 10 10 10 10 
1
10 10 1000000000
2 Likes

hey, @ssjgz u r amazing :grinning:, how do you find such test input. Please suggest how can I learn this trick.

1 Like

If you would have had a look on constraints , the a[I]<100 and N<100000 so it clearly means that the values can repeat

1 Like

Just analysis and guesswork in this particular case: I couldn’t see any out-of-bounds accesses or other sources of Undefined Behaviour, so that kind of left division by 0 as the most likely possibility. It was then a simple matter to contrive an example that triggers one :slight_smile:

2 Likes

Unable to think about this question. Pls help.
I read its editorial but stucked at cumulative frequency. What is cumulative freq and how it was calculated.
Please give some idea to solve this problem.