# Bitwise in python - O(n)

• Python automatically promotes integers to higher size. Assuming bitwise operations on larger ints are O(1), this would be O(n) solution.

``````class Solution(object):
def kEmptySlots(self, flowers, k):
"""
:type flowers: List[int]
:type k: int
:rtype: int
"""
n       = len(flowers)
pots    = 0
spacing = k + 1
for day, spot in enumerate(flowers):
pots |= (1 << spot ) # marking the pot at spot blooming
left  = spot + spacing
right = spot - spacing
if left <= n:
leftset = pots & (1<<left)
between = ( pots & (  (1 << left) - 1 ) ) >> (spot+1)
if leftset != 0 and between == 0:
return day + 1
if right >= 1:
rightset = pots & (1<<right)
between  = ( pots & ( ( 1 << spot) - 1) ) >> (right+1)
if rightset != 0 and between == 0:
return day + 1
return -1
``````

• Just curious, what's the time consuming of the bit operation `i << n`, is it O(1) or O(n)?

• @BigBiang

I think it is O(1) or constant time for ints that fit in word size of processor. For 64 bit processor, n < 64, 1 << n will be O(1), for n >= 64, i think it may be O(n/64)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.