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}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3
class Solution:
    def nextSparse (ob, n):
        # code here 

Solutions:
class Solution:

	def nextSparse(ob, n):
		while True:
			if n & n << 1 != 0:
				n += 1
			else:
				return n


class Solution:

	def nextSparse(ob, n):
		bin = []
		x = n
		while x:
			bin.append(x & 1)
			x >>= 1
		bin.append(0)
		last = 0
		for i in range(1, len(bin) - 1):
			if bin[i] == 1 and bin[i - 1] == 1 and (bin[i + 1] != 1):
				bin[i + 1] = 1
				for j in range(i, last - 1, -1):
					bin[j] = 0
				last = i + 1
		ans = 0
		for i in range(len(bin)):
			ans = ans + bin[i] * (1 << i)
		return ans


class Solution:

	def nextSparse(ob, n):

		def helper(s):
			new = s[0]
			for i in s[1:]:
				if new == '1' and i == '1':
					return False
				new = i
			return True
		for i in range(n, n * 100):
			c = bin(i)[2:]
			if helper(c):
				return i


class Solution:

	def nextSparse(ob, n):
		while True:
			if not n & n >> 1:
				return n
			n = n + 1


class Solution:

	def nextSparse(ob, n):
		d = n
		for i in range(n, n + 100000):
			b = bin(i)[2:]
			found = True
			for j in range(0, len(b) - 1):
				if b[j] == '1' and b[j + 1] == '1':
					found = False
					continue
			if found:
				d = i
				break
		return d


class Solution:

	def nextSparse(ob, n):
		arr = []
		while n > 0:
			arr.append(n & 1)
			n = n >> 1
		arr.append(0)
		point = 0
		i = 0
		two = 0
		while i < len(arr):
			if arr[i] == 0:
				if two < 2:
					two = 0
				else:
					while point < i:
						arr[point] = 0
						point += 1
					two = 0
					point = i
					arr[point] = 1
			if arr[i] == 1:
				two += 1
			i += 1
		count = 0
		ans = 0
		while len(arr) > 0:
			ans += pow(2, count) * arr.pop(0)
			count += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.nextSparse(n))


class Solution:

	def nextSparse(ob, n):
		while n & n >> 1:
			n += 1
		return n


class Solution:

	def nextSparse(ob, n):
		while True:
			bi = bin(n)[2:]
			if '11' in bi:
				n += 1
			else:
				break
		return n


class Solution:

	def nextSparse(ob, n):
		n1 = n
		n = ['0'] + list(bin(n).replace('0b', ''))
		t = 0
		ne = 0
		for i in reversed(range(1, len(n))):
			if n[i] == n[i - 1] == '1':
				t = 1
				ne = 1
			elif t == 1:
				for j in range(i, len(n)):
					n[j] = '0'
				n[i - 1] = '1'
				t = 0
		return int(''.join(n), 2) if ne == 1 else n1


class Solution:

	def nextSparse(ob, n):
		prev = -2
		for i in range(32):
			bit = 1 << i
			if n & bit > 0:
				if i - prev == 1:
					n += 1 << prev
					n &= 4294967295 << prev
					prev = -2
				else:
					prev = i
			else:
				prev = -2
		return n


class Solution:

	def nextSparse(ob, n):
		store = []
		for i in range(n):
			store.append(n & 1)
			n >>= 1
		last_changed = 0
		for i in range(1, len(store) - 1):
			if store[i - 1] == 1 and store[i] == 1 and (store[i + 1] != 1):
				store[i + 1] = 1
				for j in range(i, last_changed - 1, -1):
					store[j] = 0
				last_changed = i + 1
		ans = 0
		for i in range(len(store)):
			ans += store[i] * (1 << i)
		return ans


class Solution:

	def nextSparse(ob, n):
		bits = list(map(int, bin(n)[2:]))
		bits.reverse()
		l = len(bits)
		res = bits + [0]
		last = 0
		for i in range(1, l):
			if res[i] == res[i - 1] == 1 and res[i + 1] != 1:
				for j in range(i, last - 1, -1):
					res[j] = 0
				last = i + 1
				res[last] = 1
		ans = 0
		pwr = 0
		for e in res:
			if e:
				ans += e * 2 ** pwr
			pwr += 1
		return ans


class Solution:

	def nextSparse(ob, x):
		MAX_INT = 1000000000
		mask = 7
		dense_ending = 3
		tail = 3
		push_value = 4
		while push_value <= MAX_INT:
			if x & mask == dense_ending:
				x = (x & ~tail) + push_value
			mask = mask << 1
			dense_ending = dense_ending << 1
			push_value = push_value << 1
			tail = (tail << 1) + 1
			if x > MAX_INT:
				ob = -1
				return -1
		ob = x
		return x


class Solution:

	def nextSparse(ob, n):
		digits = []
		num = n
		while num > 0:
			digits.append(num & 1)
			num >>= 1
		digits.append(0)
		n = len(digits)
		lastFinal = 0
		for i in range(1, n - 1):
			if digits[i - 1] == digits[i] == 1 and digits[i + 1] == 0:
				digits[i + 1] = 1
				for j in range(i, lastFinal - 1, -1):
					digits[j] = 0
				lastFinal = i + 1
		ans = 0
		for i in range(n):
			ans += digits[i] * (1 << i)
		return ans


class Solution:

	def nextSparse(ob, n):
		N = n
		a = []
		while n:
			a.append(n % 2)
			n = n // 2
		a.append(0)
		l = len(a)
		flag = False
		i = l - 2
		j = 0
		while i >= 0:
			if a[i] == 1 and a[i - 1] == 1:
				while a[i] == 1 and a[i - 1] == 1:
					a[i + 1] = 1
					flag = True
					j = i
					i = i + 2
					if i >= l:
						break
				if flag:
					break
			i = i - 1
		if flag:
			for i in range(0, j + 1):
				a[i] = 0
		k = 0
		for i in range(l - 1, -1, -1):
			k = k * 2 + a[i]
		return k