1

most of the solutions which i submit in hackerrank are thrown timeout error, so i tried to find the execution time for one of the codes in sublime text 3 in my pc,and resulted in [finished in 220.5 sec] for an input of 2 million input.

problem statement: https://www.hackerrank.com/challenges/py-the-captains-room/problem

my solution: 

n=int(input())
l_list=list(map(int,(input().split())))
l_set=set(l_list)
for i in l_set:
    c=l_list.count(i)
    if c==1:
        print(i)

please help me in optimizing the code or is my system too slow???

sunil kumar
  • 11
  • 1
  • I don't think questions of type "help me reformat my code" are allowed here. Nevertheless, I think you should read on how to use the Big O notation to determine the efficiency of your code. – Taslim Oseni Jun 17 '18 at 13:20

2 Answers2

0

Your loop is O(n^2) because list.count is O(n). Also creating set is O(n) operation that you can skip.

You should think about trying to go through your array once and do all the counting. Now you are going through all of the items in set, and for each one of the items l_list.count(i) goes through the list once, this gives you horrible O(n^2) performance.

I don't want to give you straight answer, since the task is meant as a learning experience...

Andrew Morozko
  • 2,576
  • 16
  • 16
  • i actually found the solution(just a simple one line arithmetic formula using sum()), but i really wanted to know the solution , if 'n' is not fixed (or not given) !!!! – sunil kumar Jun 17 '18 at 15:32
  • @sunilkumar Here you go: comparison of a couple of different algorithms https://gist.github.com/Andrew-Morozko/04da247c4aaa7e90745db0d70ee8e13d – Andrew Morozko Jun 19 '18 at 12:56
0

I faced the same problem with my code below ..

k=int(input())
a_list=list(input().split())
a_set=set(a_list)
for each in a_set:
    if(a_list.count(each)!=k):
        print(each)

The trick is to use the Counter from collections. Refer the discussion below How to count the occurrences of a list item?

user1374085
  • 9
  • 4
  • From Review: Welcome to Stack Overflow! While links are great way of sharing knowledge, they won't really answer the question if they get broken in the future. Add to your answer the essential content of the link which answers the question. In case the content is too complex or too big to fit here, describe the general idea of the proposed solution. Remember to always keep a link reference to the original solution's website. See: [How do I write a good answer?](https://stackoverflow.com/help/how-to-answer) – sɐunıɔןɐqɐp Oct 06 '18 at 08:48