Given an array of length N, starting from 1 to N. At each iteration, you remove all elements at odd positions, until only one element is left. Find the last remaining element.
 
Example 1:
Input:
N = 5
Output:
4
Explanation:
Initial Array- {1,2,3,4,5}.
After 1st Iteration- {2,4}.
After 2nd Interation- {4}
Threfore, the answer is 4.
Example 2:
Input:
N = 3
Output:
2
Explanation:
Initial Array- {1,2,3}.
After 1st Iteration- {2}.
Threfore, the answer is 2.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function oddGame() which takes an Integer N as input and returns the last remaining element.
 
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{9}

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def oddGame(self, N):

        # code here

Solutions:
import math

class Solution:

	def oddGame(self, N):
		if N == 1:
			return 1
		c = int(math.log2(N))
		return 1 << c


class Solution:

	def oddGame(self, N):
		ans = 1
		while ans <= N:
			ans *= 2
		return ans // 2


class Solution:

	def oddGame(self, N):
		if N == 1:
			return 1
		return self.oddGame(N // 2) * 2


class Solution:

	def oddGame(self, N):
		a = 1
		if N == 1:
			return N
		else:
			N = N // 2
			while N >= 1:
				N //= 2
				a *= 2
			return a


class Solution:

	def oddGame(self, n):
		import math
		return 2 ** math.floor(math.log(n, 2))
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.oddGame(N))


class Solution:

	def oddGame(self, N):
		if N == 0:
			return
		arr = range(1, N + 1)
		if N == 1:
			return arr[0]
		while len(arr) != 1:
			arr = arr[1:N - 1:2]
		return arr[0]
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.oddGame(N))


class Solution:

	def oddGame(self, N):
		gap = 1
		length = N
		temp = N
		while length > 1:
			if length % 2 != 0:
				temp = temp - gap
			gap = gap * 2
			length = int(length / 2)
		return temp
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.oddGame(N))


class Solution:

	def oddGame(self, n):
		num = 1
		while num <= n:
			num *= 2
		return num // 2


class Solution:

	def oddGame(self, N):
		if N & N - 1 == 0:
			return N
		binVal = bin(N)[2:]
		nearestPow2 = '1' + '0' * (len(binVal) - 1)
		return int(nearestPow2, 2)


class Solution:

	def oddGame(self, N):
		from math import log
		return 2 ** int(log(N, 2))


class Solution:

	def oddGame(self, N):
		c = 0
		while N != 0:
			c += 1
			N = N // 2
		return 2 ** (c - 1)


class Solution:

	def oddGame(self, N):
		ans = 1
		if N == 1:
			return N
		while N > 1:
			ans = ans << 1
			N = N >> 1
		return ans


from math import pow

class Solution:

	def oddGame(self, N):
		if N == 1:
			return 1
		return self.oddGame(N // 2) * 2


import math

class Solution:

	def oddGame(self, N):
		return pow(2, int(math.log2(N)))


class Solution:

	def oddGame(self, N):
		ans = 1
		while ans <= N:
			ans *= 2
		if ans != 1:
			ans = ans / 2
		return int(ans)


class Solution:

	def oddGame(self, N):
		if N == 1:
			return 1
		else:
			return 2 * self.oddGame(int(N / 2))


class Solution:

	def oddGame(self, N):
		import math
		return 2 ** math.floor(math.log2(N))


import math

class Solution:

	def oddGame(self, N):
		ans = math.log(N, 2)
		return 2 ** int(ans // 1)


import math

class Solution:

	def power(self, num, exp):
		result = 1
		while exp:
			if exp % 2 == 0:
				num = num * num
				exp = exp // 2
			else:
				result = num * result
				exp = exp - 1
		return result

	def oddGame(self, N):
		log = 0
		while N > 1:
			log += 1
			N = N // 2
		return self.power(2, log)


import math

class Solution:

	def oddGame(self, N):
		log = 0
		while N > 1:
			log += 1
			N = N // 2
		return 2 ** log


def fun(n):
	if n == 1:
		return n
	return fun(n // 2) * 2

class Solution:

	def oddGame(self, n):
		a = fun(n)
		return a


class Solution:

	def oddGame(self, N):
		if N == 1:
			return 1
		t = 1
		while 2 ** t <= N:
			t += 1
		return 2 ** (t - 1)


class Solution:

	def oddGame(self, n):
		pow = math.log(n) // math.log(2)
		ans = 1
		x = 2
		while pow > 0:
			if pow % 2 == 1:
				ans *= x
				pow -= 1
			else:
				x *= x
				pow = pow // 2
		return ans


class Solution:

	def oddGame(self, N):
		b = bin(N)[2:]
		return 2 ** (len(b) - 1)


class Solution:

	def oddGame(self, n):
		if n == 1:
			return 1
		return self.oddGame(n // 2) * 2


class Solution:

	def oddGame(self, N):
		a = int(math.log2(N))
		ans = int(math.pow(2, a))
		return ans


class Solution:

	def oddGame(self, N):
		return max(1, pow(2, math.floor(math.log(N, 2))))


class Solution:

	def oddGame(self, N):
		if N in (1, 2):
			return N
		num = 2
		while True:
			if num > N:
				break
			prev = num
			num = num * 2
		return prev


class Solution:

	def oddGame(self, N):
		power = 0
		while N > 1:
			if N % 2 == 0:
				N = N / 2
			else:
				N = (N - 1) / 2
			power = power + 1
		return pow(2, power)


class Solution:

	def oddGame(self, n):
		return 2 ** (len(bin(n)[2:]) - 1)


class Solution:

	def oddGame(self, n):
		i = 0
		while n // 2 > 0:
			n = n // 2
			i += 1
		return 2 ** i


class Solution:

	def oddGame(self, N):
		number = 1
		while N > 1:
			N = N >> 1
			number = number << 1
		return number


class Solution:

	def oddGame(self, N):
		n = 0
		while N > 0:
			N = N >> 1
			n += 1
		return 1 << n - 1


class Solution:

	def oddGame(self, N):

		def recur(N, i):
			if N == 1:
				return i
			return recur(N // 2, 2 * i)
		return recur(N, 1)


class Solution:

	def removeElementsAtOddPositions(self, array):
		index = len(array) - 1
		if index % 2 == 1:
			index = index - 1
		while index >= 0:
			del array[index]
			index = index - 2

	def makeArray(self, N):
		array = []
		i = 2
		while i <= N:
			array.append(i)
			i = i + 2
		return array

	def oddGame(self, N):
		x = 1
		while N > 1:
			N = N // 2
			x = x * 2
		return x


class Solution:

	def oddGame(self, N):
		i = 0
		while pow(2, i) <= N:
			i += 1
		return pow(2, i - 1)