Performing add/delete/count operations on a list Problem Statement (HackerRank)
  
  You have a list of integers, initially the list is empty.
  
  You have to process Q operations of three kinds:
  
  
  add s: Add integer s to your list, note that an integer can exist more
  than one time in the list
  del s: Delete one copy of integer s from the list, it's guaranteed
  that at least one copy of s will exist in the list.
  cnt s: Count how many integers a are there in the list such that a AND
  s = a, where AND is bitwise AND operator
  
  
  Input Format
  
  First line contains an integer Q.  Each of the following Q lines
  contains an operation type string T and an integer s.
  
  Constraints  
  
  
  \$1 \le Q \le 200000\$
  \$0 \le s \lt 2^{16}\$
  
  
  Output Format
  
  For each cnt s operation, output the answer in a new line.
  
  Sample Input

7 
add 11 
cnt 15 
add 4 
add 0 
cnt 6 
del 4 
cnt 15

  
  Sample Output

1 
2 
2

  
  Explanation
  
  For first line, we have 15 AND 11 = 11 so the answer is 1
  
  For second line, 6 AND 0 = 0 and 6 AND 4 = 4 so the answer is 2
  
  For third line, 4 has been deleted and we have 15 AND 11 = 11 and 15
  AND 0 = 0 so the answer is 2


My working code:

operations = int(raw_input())
current = 1
lst = []
while current &lt;= operations:
    count = 0
    input_ = raw_input().split()
    operation = input_[0]
    num = int(input_[1])
    if operation == 'add':
        lst.append(num)
    elif operation == 'cnt':
        for number in lst:
            if number &amp; num == number:
                count += 1
        print(count)
    elif operation == 'del':
        lst.remove(num)
    current += 1
You don't exploit the nature of the question.


  Constraints
  
  
  \$1 \le Q \le 200000\$
  \$0 \le s \lt 2 ^ {16}\$
  


Why are these important? It's so you can achieve greater performance, for a price in memory.

You know that there is \$2 ^ {16}\$ possible numerical inputs,
and there is a maximum of 200000 inputs.

If the last input is count, and all the rest are add,
you will be recounting numbers a lot. Leading to a dramatic performance loss.

First you would want to prevent recounting if possible.
One way to do this is to make a dictionary to count the occurrences of numbers.
However due to constant type changes you can just use a list instead.

lst = [0] * (2 ** 16)


This takes more time than using lst = [], but it will pay off.



If we look at the performance of your 3 functions.
I use the information from Python's time complexity page.

Add

lst.append(num)


This is average case \$O(1)\$, worst case \$O(n)\$, (not amortized worst case).

lst is internally stored as an array,
and so if you grow past the bounds all the data must move.

And so I will say this is \$O(n)\$.

Del

lst.remove(num)


This is average case \$O(n)\$, worst case \$O(n)\$.

And so this is \$O(n)\$.

cnt

for number in lst:
    if number &amp; num == number:
        count += 1
print(count)


And again this is \$O(n)\$.

Overall

You can have 200000 calls to functions that are \$O(n)\$.
If you ask me that's not good on performance.



You can easly make add and del \$O(1)\$.

If you use lst = [0] * (2 ** 16).

if operation == 'add':
    lst[num] += 1
elif operation == 'del':
    lst[num] -= 1


It's like using a default-dictionary where the index is only numbers.
However this currently will have the drawback of cnt always being \$O(2 ^ {16})\$.

If you wish to fix that you can use a set, to store the numbers, so it is \$O(n)\$.

Here is a solution that passes a few more of the tests. It does not pass them all.

operations = int(raw_input())
nums = set()
storage = [0] * (2 ** 16)

for _ in xrange(operations): 
    input_ = raw_input().split()
    operation = input_[0]
    num = int(input_[1])

    if operation == 'add':
        nums |= {num}
        storage[num] += 1
    elif operation == 'cnt':
        print(sum(
            storage[number]
            for number in nums
            if (number &amp; num) == number
        ))
    elif operation == 'del':
        storage[num] -= 1


This uses a similar solution as yours, my lst is nums.
However, I aimed at obtaining \$O(1)\$ in both add and del.



I can't complete the problem.
The way Python programmers that solved this use [0] * (2 ** 16) and binary logic I don't know. Which make all the functions \$O(256)\$.