Some people(n) are standing in a queue. A selection process follows a rule where people standing on even positions are selected. Of the selected people a queue is formed and again out of these only people on even position are selected. This continues until we are left with one person. Find out the position of that person in the original queue.
Example 1:
Input: n = 5
Output: 4 
Explanation: 1,2,3,4,5 -> 2,4 -> 4.
Example 2:
Input: n = 9
Output: 8
Explanation: 1,2,3,4,5,6,7,8,9
->2,4,6,8 -> 4,8 -> 8. 
Your Task:  
You dont need to read input or print anything. Complete the function nthPosition() which takes n as input parameter and returns the position(original queue) of that person who is left.
Expected Time Complexity: O(logn)
Expected Auxiliary Space: O(1)
Constraints:
1<= n <=10^{8}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Complete search

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

Solutions:
class Solution:

	def nthPosition(self, n):
		res = 0
		for i in range(n, 0, -1):
			if i & i - 1 == 0:
				res = i
				break
		return res


class Solution:

	def nthPosition(self, n):
		ans = 0
		while n > 1:
			ans += 1
			n //= 2
		return pow(2, ans)


class Solution:

	def nthPosition(self, n):
		a = []
		for i in range(2, n + 1, 2):
			a.append(i)
		while len(a) != 1:
			t = []
			for i in range(1, len(a), 2):
				t.append(a[i])
			a[:] = t[:]
		return a[0]


class Solution:

	def nthPosition(self, n):
		i = 1
		return self.find(n, i)

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


import math

class Solution:

	def nthPosition(self, n):
		x = int(math.log2(n))
		return 2 ** x


class Solution:

	def nthPosition(self, n):

		def help(count, n):
			if n <= 1:
				return 2 ** count
			count += 1
			return help(count, n // 2)
		return help(0, n)


class Solution:

	def nthPosition(self, n):
		arr = [i for i in range(2, n + 1, 2)]
		while len(arr) > 1:
			temp = []
			for i in range(1, len(arr), 2):
				temp.append(arr[i])
			arr = temp
		return arr[0]


class Solution:
	op = []

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


class Solution:

	def nthPosition(self, n):
		for i in range(33):
			if 2 ** i > n:
				return 2 ** (i - 1)


from math import log

class Solution:

	def nthPosition(self, n):
		res = int(log(n, 2))
		return int(pow(2, res))


class Solution:

	def solve(self, i, n):
		if 2 ** i > n:
			return 2 ** (i - 1)
		return self.solve(i + 1, n)

	def nthPosition(self, n):
		return self.solve(0, n)


class Solution:

	def nthPosition(self, n):
		if n == 1:
			return 0
		res = 1
		while n // 2 != 1:
			n = n // 2
			res *= 2
		return res * 2


class Solution:

	def nthPosition(self, n):
		if n == 1:
			return int(n)
		p = 1
		while p < n:
			p *= 2
			if p == n:
				return int(p)
		return int(p / 2)


class Solution:

	def nthPosition(self, n):
		i = 0
		while n >= 2 ** i:
			i += 1
		return 2 ** i if 2 ** i <= n else 2 ** (i - 1)


class Solution:

	def solve(self, n, i):
		if n < i:
			return i // 2
		return self.solve(n, i * 2)

	def nthPosition(self, n):
		return self.solve(n, 2)


class Solution:

	def solution(self, arr):
		if len(arr) == 1:
			return arr
		return self.solution(arr[1::2])

	def nthPosition(self, n):
		lst = list(range(1, n + 1))
		x = self.solution(lst)
		return x[-1]


class Solution:

	def nthPosition(self, n):
		l = []
		for i in range(1, n + 1):
			l.append(i)
		p = self.even(l)
		return p

	def even(self, l):
		if len(l) == 1:
			return l[0]
		return self.even(l[1::2])


import math

class Solution:

	def nthPosition(self, n):
		largestPower = int(math.log(n, 2))
		return int(math.pow(2, largestPower))


class Solution:

	def nthPosition(self, x):
		x |= x >> 1
		x |= x >> 2
		x |= x >> 4
		x |= x >> 8
		x |= x >> 16
		return x ^ x >> 1


class Solution:

	def nthPosition(self, n):

		def f(arr):
			if len(arr) == 1:
				return arr[0]
			return f(arr[1::2])
		l = []
		for i in range(1, n + 1):
			l.append(i)
		return f(l)


class Solution:

	def nthPosition(self, n):

		def f(arr):
			if len(arr) == 1:
				return arr[0]
			return f(arr[1::2])
		return f(list(range(1, n + 1)))


class Solution:

	def nthPosition(self, n):
		for x in range(n, 0, -1):
			if x & x - 1 == 0:
				return x


class Solution:

	def nthPosition(self, n):

		def g(a, count):
			if a == 1:
				return count
			a = int(a / 2)
			count += 1
			return g(a, count)
		return pow(2, g(n, 0))


import math

class Solution:

	def nthPosition(self, n):
		logVal = math.log2(n)
		out = 2 ** int(logVal)
		return out


class Solution:

	def nthPosition(self, n):

		def fun(ans, n, k):
			if n == 1:
				return ans
			if n % 2 == 0:
				ans = ans
			if n % 2 != 0:
				ans = ans - k
			k = k * 2
			return fun(ans, n // 2, k)
		k = 1
		ans = n
		return fun(ans, n, k)


def cullu(n):
	if n == 1:
		return 1
	c = 1 + cullu(n // 2)
	return c

class Solution:

	def nthPosition(self, n):
		c = cullu(n)
		return 2 ** (c - 1)


class Solution:

	def nthPosition(self, n):
		count = 0
		while n != 1:
			n = n // 2
			count += 1
		return 2 ** count


class Solution:

	def nthPosition(self, n):
		i = 0
		l = []
		while 1:
			if pow(2, i) <= n:
				l.append(pow(2, i))
			else:
				break
			i += 1
		return l[-1]


class Solution:

	def nthPosition(self, n):
		i = 1
		while i * 2 <= n:
			i *= 2
		return i


class Solution:

	def nthPosition(self, n):
		(i, c) = (0, 0)
		while c <= n:
			x = c
			c = pow(2, i)
			if c > n:
				break
			i += 1
		return x


class Solution:

	def nthPosition(self, n):
		temp = n
		c = 1
		while n > 1:
			if n % 2 == 0:
				n = n - n // 2
			else:
				temp = temp - c
				n = temp
		return temp


class Solution:

	def nthPosition(self, n):
		l = []
		for i in range(1, n // 2):
			if 2 ** i == n:
				return n
				break
			elif 2 ** i > n:
				return 2 ** (i - 1)
				break


class Solution:

	def nthPosition(self, n):
		c = 0
		while n:
			c += 1
			n = n >> 1
		return 2 ** (c - 1)


class Solution:

	def nthPosition(self, n):
		import math as m
		s = int(m.sqrt(n)) + 1
		i = 0
		while 2 ** i <= n:
			i += 1
		return 2 ** (i - 1)


import math

class Solution:

	def nthPosition(self, n):
		return 2 ** math.floor(math.log2(n))


class Solution:

	def nthPosition(self, n):

		def helper(i, n):
			if i > n:
				return int(i / 2)
			else:
				i = i * 2
				return helper(i, n)
		return helper(1, n)


class Solution:

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


class Solution:

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


class Solution:

	def nthPosition(self, n):
		import math
		ans = math.log(n) / math.log(2)
		return math.floor(math.pow(2, math.floor(ans)))


class Solution:

	def nthPosition(self, n):
		l = [i for i in range(2, n + 1, 2)]

		def solve(lst):
			if len(lst) <= 1:
				return lst
			nl = []
			for i in range(1, len(lst), 2):
				nl.append(lst[i])
			return solve(nl)
		return solve(l)[0]


class Solution:

	def nthPosition(self, n):
		if n == 1:
			return 1
		arr = [i for i in range(2, n + 1, 2)]

		def pos(arr):
			if len(arr) == 1:
				return arr[0]
			res = [arr[i] for i in range(1, len(arr), 2)]
			return pos(res)
		return pos(arr)


class Solution:

	def nthPosition(self, n):

		def position(i, n):
			if i > n:
				return i // 2
			i = i * 2
			return position(i, n)
		return position(1, n)


import math

class Solution:

	def nthPosition(self, n):
		return 1 << int(math.log2(n))


class Solution:

	def nthPosition(self, n):
		if n < 3:
			return n
		else:
			return 2 * self.nthPosition(n // 2)


class Solution:

	def nthPosition(self, n):
		list1 = [i for i in range(1, n + 1, 1)]
		new = []
		while len(list1) > 1:
			new = [list1[i] for i in range(1, len(list1), 2)]
			list1[:] = new[:]
		return list1[0]


import math

class Solution:

	def nthPosition(self, n):
		x = int(math.log(n) / math.log(2))
		y = 2 ** x
		return y


import sys

class Solution:

	def nthPosition(self, n):
		if n < 1:
			return 0
		res = 1
		for i in range(8 * sys.getsizeof(n)):
			curr = 1 << i
			if curr > n:
				break
			res = curr
		return res


import math

class Solution:

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


class Solution:

	def nthPosition(self, n):
		if n == 1:
			return 1
		nth_pos = 2
		while n >= nth_pos:
			nth_pos *= 2
		return nth_pos // 2


import math

class Solution:

	def nthPosition(self, n):
		c = int(math.log(n, 2))
		d = int(pow(2, c))
		return d


class Solution:

	def __init__(self):
		self.k = 1

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


class Solution:

	def nthPosition(self, n):
		s = bin(n)
		bits = len(s) - 2
		num = '1'
		for i in range(bits - 1):
			num += '0'
		return n & int(num)


class Solution:

	def nthPosition(self, n):
		ans = 1
		while n != 1:
			ans = 2 * ans
			n //= 2
		return ans


class Solution:

	def nthPosition(self, n):
		l = 2
		if n & 1:
			r = n - 1
		else:
			r = n
		diff = r - l
		i = 1
		while diff > 0:
			i *= 2
			l = l + i
			r = r - i
			diff = r - l
		return l


class Solution:

	def nthPosition(self, n):
		list1 = [j for j in range(1, n + 1)]

		def ans(list1):
			if len(list1) == 1:
				return list1[0]
			list1 = [list1[j] for j in range(1, len(list1), 2)]
			return ans(list1)
		return ans(list1)


class Solution:

	def nthPosition(self, n):
		x = str(bin(n))[2:]
		ans = pow(2, len(x) - 1)
		return ans


class Solution:

	def nthPosition(self, n):
		l = []
		for i in range(n):
			l.append(i + 1)
		while len(l) != 1:
			b = l[1::2]
			l = b[:]
		return l[0]


class Solution:

	def nthPosition(self, n):
		return 1 << n.bit_length() - 1


import math

class Solution:

	def nthPosition(self, n):
		if n == 1:
			return 1
		n = int(math.log(n, 2))
		return pow(2, n)


import math

class Solution:

	def nthPosition(self, n):
		p = int(math.log(n, 2))
		return int(pow(2, p))
		return even(n)


class Solution:

	def nthPosition(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		else:
			start = 2
			while start <= n:
				if start * 2 <= n:
					start = start * 2
				else:
					return start


class Solution:

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