PiStroke's blog

By PiStroke, history, 2 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    Actually thinking about it, you can find the number of set bits implicitly.

    Code would be something like this:

    import sys
    input = sys.stdin.readline
    a = [int(x) for x in input().split()]
    arr = [0] * (10**9 // 32)
    ans = 0
    for x in a:
        i = x // 32
        j = x % 32
        ans -= (arr[i] >> j) & 1
        arr[i] |= 1 << j
        ans += 1
    print(ans)
    
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is an array module contains arrays as same as c arrays and contains bool array.

from array import array
vis=array('b',[0]*10)   # 'b' mean bool variable

You can see more about this arrays in my previous blog