Is it possible to solve this problem in O(n) given that the numbers can only be in the range from 1 to 1000?
P.S: I tried solving this in O(n) but I am getting WA. I also created a random input generator and compared my output with the correct code for n = 100 and values from 1 to 100 but didn't find any difference.
My Code
Add this in front of your AC code like
or
Hence a contradiction because its constraint is $$$1 \leq a_i \leq 1000$$$
And yes, your Linear solution is correct, I tested yours with hundred of test cases
Fun fact: Geeksforgeek's wrong solution killed a red ranker once in a contest :D
Haha! Their codes aren't very reliable.
Thank you so much! This was really helpful :)