Little Elephant and Divisors - LEDIV

Problem link : LEDIV

My code : LEDIV

Can’t figure out the error in my code. Please help.

Have you understood the problem clearly?
Have you read the editorial?

Your program is printing only one output for 2 test inputs.

Updated my code.

My algorithm is incorrect. It fails for n = 1 because the for loop staarts from j = 2 and the inner loop terminates when a[i] % j != 0 and directly compares the value of ans and n. This will cause the output to be -1 for all sequences which contain an odd number.

Your code at IdeOne is wrong, isn’t it? T = 5, but there are 4 results in output…

@betlista Yes that code is incorrect and no I now the reason it fails, so I am trying some other method.

This solution is getting TLE.

First observation, why are you using sort to get min, when sort is O(n log n) but array traversal is O(n)…

1 Like

@betlista Still getting TLE. Should I use getchar_unlocked ?

Such optimizations are not needed when algorithm is ok :wink:

Your code runs in O(min(a[i]) * n), so for 100.000 * 100.000 it requires 10^10 operations.

And what is the limit for Codechef judge?

I do not know for sure, but I guess something like 10^8 for second.