Problem statement

https://binarysearch.com/problems/Next-Binary-Permutation/

Solution

Variation of Leetcode 0031. Next Permutation, but here we need to add some extra zeroes in the beginning.

Complexity

It is O(32) for time and space.

Code

class Solution:
    def solve(self, n):
        nums = ["0"]*30 + [i for i in bin(n)[2:]]
        
        def reverse(L, start, end):
            while start < end:
                L[start], L[end] = L[end], L[start]
                start, end = start + 1, end - 1
        
        i, n = len(nums) - 1, len(nums)
        while i >= 1 and nums[i] <= nums[i-1]:
            i -= 1
            
        if i != 0:
            j = i
            while j + 1 < n and nums[j+1] > nums[i - 1]:
                j += 1
            
            nums[i-1], nums[j] = nums[j], nums[i-1]
        
        reverse(nums, i, n - 1)
        
        return int("".join(nums), 2)