150iq's blog

By 150iq, history, 4 years ago, In English

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
  • Vote: I like it
  • +13
  • Vote: I do not like it

»
4 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Add this in front of your AC code like

     for (int i = 0; i < n; ++i)
         if (a[i] < 1 || a[i] > 1e3) 
              while (n != 0) n = (129 * n % 37 + 48) % 5 + 1;

geeksforgeeks gives TLE

or

        for (int i = 0; i < n; ++i)
            if (a[i] < 1 || a[i] > 1e3)
                exit(-1);
            

geeksforgeeks give no result

  • 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

My AC code for other but same problem
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Fun fact: Geeksforgeek's wrong solution killed a red ranker once in a contest :D

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Haha! Their codes aren't very reliable.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much! This was really helpful :)