Given a positive integer N. The problem is to print the numbers in the range 1 to n having bits in alternate pattern. Here alternate pattern means that the set and unset bits in the number occur in alternate order. For example- 5 has an alternate pattern i.e. 101.
Example 1:
Input:
N = 10
Output: 1 2 5 10
Explanation:
Binary representation of 1 : 0001
Binary representation of 2 : 0010
Binary representation of 5 : 0101
Binary representation of 10 : 1010
Here, We can see that the bits 
pattern in all the above configuration 
is alternate. So, we return an array
having {1, 2, 5 and 10}. 
 
Example 2:
Input:
N = 50
Output: 1 2 5 10 21 42
Your Task:  
You don't need to read input or print anything. Your task is to complete the function printNumHavingAltBitPatrn() which takes the integer N as input parameters and returns an array of integers with alternate bits in the range 1 to N.
Expected Time Complexity: O(log(n))
Expected Auxiliary Space: O(1)
 
CONSTRAINTS:
1<= N <=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

    def count (self, N):

        # code here





Solutions:
class Solution:

	def count(self, N):
		ans = []
		n = 1
		m = 0
		while n <= N:
			ans.append(n)
			n = (n << 1) + m
			m = 1 - m
		return ans


class Solution:

	def count(self, N):
		l = [1]
		i = 1
		while l[-1] <= N:
			if i % 2 == 1:
				l.append(l[-1] * 2)
			else:
				l.append(l[-1] * 2 + 1)
			i += 1
		return l[:-1]


class Solution:

	def count(self, N):
		output = []
		num = '10' * 16
		i = 1
		while True:
			item = int(num[:i], 2)
			if item > N:
				break
			i += 1
			output.append(item)
		return output


class Solution:

	def count(self, N):
		c = 0
		x = []
		while True:
			if c % 2 == 0:
				c = c * 2 + 1
			else:
				c = c * 2
			if c > N:
				break
			x.append(c)
		return x


class Solution:

	def count(self, n):
		curr_num = 1
		res = []
		res.append(curr_num)
		while 1:
			curr_num = curr_num << 1
			if n < curr_num:
				break
			res.append(curr_num)
			curr_num = curr_num << 1 ^ 1
			if n < curr_num:
				break
			res.append(curr_num)
		return res


class Solution:

	def count(self, N):
		count = 0
		current = 1
		ans = [1]
		for i in range(N):
			current *= 2
			if count % 2 == 1:
				current += 1
			if current > N:
				break
			count += 1
			ans.append(current)
		return ans


class Solution:

	def count(self, N):
		ls = [1]
		while True:
			num = 0
			if ls[-1] % 2 == 0:
				num = ls[-1] + ls[-1] + 1
			else:
				num = ls[-1] + ls[-1]
			if num > N:
				break
			else:
				ls.append(num)
		return ls


class Solution:

	def count(self, N):
		temp = []
		for i in range(1, N + 1):
			x = i ^ i >> 1
			if x & x + 1 == 0:
				temp.append(i)
		return temp


class Solution:

	def count(self, N):
		n = []
		k = ['1']
		j = 1
		while 2 ** (j - 1) <= N:
			while len(k) < j:
				if k[-1] == '1':
					k.append('0')
				else:
					k.append('1')
			n.append(eval('0b' + ''.join(k)))
			j = j + 1
		if n[-1] > N:
			n.pop()
		return n


class Solution:

	def count(self, N):
		i = 1
		l = []
		while i <= N:
			l.append(i)
			if i % 2:
				i = i * 2
			else:
				i = i * 2 + 1
		return l
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		N = int(input())
		ans = ob.count(N)
		print(*ans)


class Solution:

	def count(self, N):
		num = 1
		i = 0
		res = []
		while num <= N:
			res.append(num)
			num = num << 1
			if i % 2 == 1:
				num |= 1
			i += 1
		return res


class Solution:

	def count(self, N):
		index = 2
		previous = 1
		result = [previous]
		while True:
			if index & 1:
				previous = previous * 2 + 1
			else:
				previous = previous * 2
			if previous > N:
				break
			result.append(previous)
			index += 1
		return result


class Solution:

	def count(self, N):
		x = 0
		count = 0
		ans = []
		while x < N:
			if count & 1 == 0:
				x = x << 1
				x |= 1
			else:
				x = x << 1
			count += 1
			if x <= N:
				ans.append(x)
		return ans


class Solution:

	def count(self, N):
		temp = 1
		res = []
		while temp <= N:
			res.append(temp)
			if temp % 2 == 1:
				temp *= 2
			else:
				temp = 2 * temp + 1
		return res