Bitwise in python - O(n)


  • 2
    S

    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
    

  • 0

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


  • 0
    S

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


Log in to reply
 

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