Given an integer n in the input, find its next sparse binary number.A sparse binary number is a number whose binary representation does not contain any consecutive 1s.
Example 1:
Input: n = 3
Output: 4
Explanation: Binary representation of 4
is 0100.
Example 2:
Input: n = 5
Output: 5
Explanation: Binary representation of 5
is 0101.
Your Task:
You dont need to read input or print anything. Complete the function nextSparse() which takes n as input parameter and returns the next sparse binary number.
Expected Time Complexity: O(logn)
Expected Auxiliary Space: O(logn)
Constraints:
1<= n <=10^{5}

见题面

见题面