Recently, I came across this blog which explains bitwise operations in vector <bool> (c++).
Problem: You are given 10**7 integers in the range [0,10**9], find the number of distinct integers.
In python making a boolean list/array wouldn't help, an integer will occupy at least 24 bits and a bool will occupy 8 bits, the issue is it would lead to MLE, which isn't desirable!
Are there any python alternatives for vector <bool>?
I looked up numPy (even though it's not allowed in online Judge) but it doesn't seem to have one. Bitarray might be of some help, but I believe it's not allowed in Online Judge either.
You can make a bootleg std::bitset in python, make an array(let's call it just arr) of 10**9/32 integers, and do arr[x // 32] |= 1 << (x % 32) for every x in input array. Then afterwards you find number of 1 bits in all elements of arr.
Btw I am not sure about the complexity of doing so, in C++ you can count 1 bits in O(1). If that's not the case in Python, then you probably can't do the problem in python without getting TLE, a better try would be to put input array through a set and find its length.
Actually thinking about it, you can find the number of set bits implicitly.
Code would be something like this:
There is an array module contains arrays as same as c arrays and contains bool array.
You can see more about this arrays in my previous blog