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)?
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)