Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle in a fixed direction.
After each operation, the count will start from k+1th person. The task is to choose the safe place in the circle so that when you perform these operations starting from 1st place in the circle, you are the last one remaining and survive.
Example 1:
Input:
n = 3 k = 2
Output: 3
Explanation: There are 3 persons so 
skipping 1 person i.e 1st person 2nd 
person will be killed. Thus the safe 
position is 3.
 
Example 2:
Input:
n = 5 k = 3
Output: 4
Explanation: There are 5 persons so 
skipping 2 person i.e 3rd person will 
be killed. Thus the safe position is 4.
 
Your Task:
You don't need to read input or print anything. You are required to complete the function josephus () that takes two parameters n and k and returns an integer denoting safe position. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= k, n <= 20

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Complete search

Starter code: #Complete this function



class Solution:

    def josephus(self,n,k):

        #Your code here

Solutions:
class Solution:

	def josephus_(self, n, k):
		if n == 0:
			return 0
		else:
			return (self.josephus_(n - 1, k) + k) % n

	def josephus(self, n, k):
		return self.josephus_(n, k) + 1


class Solution:

	def josephus(self, n, k):
		if n == 1:
			return 1
		else:
			return (self.josephus(n - 1, k) + k - 1) % n + 1


class Solution:

	def josephus(self, n, k):
		arr = [0] * n
		for i in range(n):
			arr[i] = i + 1
		index = 0
		while len(arr) > 1:
			index = (index + k - 1) % n
			del arr[index]
			n -= 1
		return arr[0]


class Solution:

	def josephus(self, n, k):

		def recursive(n, k):
			if n == 1:
				return 0
			return (recursive(n - 1, k) + k) % n
		return recursive(n, k) + 1


class Solution:

	def josephus(self, n, k):
		ind_list = []
		ans = [-1]
		for i in range(1, n + 1):
			ind_list.append(i)
		k = k - 1
		index = 0
		self.solve(ind_list, k, index, ans)
		return ans[0]

	def solve(self, ind_list, k, index, ans):
		if len(ind_list) == 1:
			ans[0] = ind_list[0]
			return
		index = (index + k) % len(ind_list)
		ind_list.pop(index)
		self.solve(ind_list, k, index, ans)


from collections import deque

class Solution:

	def josephus(self, n, k):
		q = deque()
		for i in range(n):
			q.appendleft(i + 1)
		while len(q) != 1:
			for i in range(k - 1):
				ele = q.pop()
				q.appendleft(ele)
			q.pop()
		return q[0]


class Solution:

	def josephus(self, n, k):
		siguiente = 0
		quedan = []
		for i in range(1, n + 1):
			quedan += [i]
		while len(quedan) > 1:
			se_va = (siguiente + k - 1) % len(quedan)
			quedan.pop(se_va)
			siguiente = se_va % len(quedan)
		return quedan[0]


class Solution:

	def josephus(self, n, k):
		arr = [i for i in range(1, n + 1)]

		def recur(arr, idx, k):
			if len(arr) == 1:
				return arr[0]
			l = len(arr)
			arr.pop((idx + k - 1) % l)
			return recur(arr, (idx + k - 1) % l, k)
		return recur(arr, 0, k)


class Solution:

	def josephus(self, n, k):
		l = [i for i in range(1, n + 1)]
		ind = 0
		while len(l) > 1:
			ind = (ind + k - 1) % len(l)
			l.remove(l[ind])
		return l[0]


def fun(n, k):
	if n == 1:
		return 1
	else:
		x = (fun(n - 1, k) + k) % n
		if x == 0:
			return n
	return x

class Solution:

	def josephus(self, n, k):
		l = fun(n, k)
		return l


class Solution:

	def josephus(self, n, k):
		people = list(range(1, n + 1))
		index = 0
		while len(people) > 1:
			index = (index + k - 1) % len(people)
			people.pop(index)
		return people[0]


class Solution:

	def josephus(self, n, k):
		arr = [i + 1 for i in range(n)]
		start = 0
		for i in range(n - 1):
			idx = (start + k - 1) % len(arr)
			arr.remove(arr[idx])
			start = idx % len(arr)
		return arr[0]


class Solution:

	def josephus(self, n, k):
		prev = 0
		for i in range(2, n + 1):
			prev = (prev + k) % i
		return prev + 1


class Solution:

	def josephus(self, n, k):
		arr = [i for i in range(1, n + 1)]
		total = n
		start = 0
		k -= 1
		while total != 1:
			rem = (start + k) % total
			del arr[rem]
			total -= 1
			start = rem
		return arr[0]


class Solution:

	def josephus(self, n, k):
		li = [i for i in range(1, n + 1)]
		pos = 0
		while len(li) != 1:
			pos = (pos + k - 1) % len(li)
			del li[pos]
		return li[0]


class Solution:

	def josephus(self, n, k):
		l = [i for i in range(1, n + 1)]
		i = 0
		while 1:
			le = len(l)
			if le == 1:
				return l[0]
			i = (i + k - 1) % le
			l.pop(i)


class Solution:

	def josephus(self, n, k):
		if n == 1:
			return 1
		x = self.josephus(n - 1, k)
		return (x + k - 1) % n + 1


class Solution:

	def josephus(self, n, k):
		i = 1
		ans = 0
		while i <= n:
			ans = (ans + k) % i
			i += 1
		return ans + 1


class Solution:

	def josephus(self, n, k):
		ans = self.dummy(n, k)
		return ans + 1

	def dummy(self, n, k):
		if n == 1:
			return 0
		return (self.dummy(n - 1, k) + k) % n


class Solution:

	def josephus(self, n, k):
		l = list(range(n))

		def recursive(i=0):
			if len(l) == 1:
				return l[0] + 1
			i = (i + k - 1) % len(l)
			l.pop(i)
			return recursive(i % len(l))
		return recursive()


class Solution:

	def josephus(self, n, k):
		rem = 0
		plist = list(range(1, n + 1, 1))
		for i in range(n - 1):
			if rem + k - 1 < len(plist):
				rem = rem + k - 1
				plist.pop(rem)
			else:
				rem = rem + k - 1
				rem = rem % len(plist)
				plist.pop(rem)
		return plist[0]


class Solution:

	def josephus(self, n, k):
		arr = list(range(0, n))

		def recurs(i):
			if len(arr) == 1:
				return arr[0] + 1
			if i >= len(arr):
				i = i % len(arr)
			arr.pop(i)
			i += k - 1
			return recurs(i)
		return recurs(0 + k - 1)


class Solution:

	def josephus(self, n, k):

		def Solve(nums, ind, k):
			if len(nums) == 1:
				return nums[0]
			ind = (ind + k - 1) % len(nums)
			nums.pop(ind)
			return Solve(nums, ind, k)
		nums = [x for x in range(1, n + 1)]
		return Solve(nums, 0, k)


class Solution:

	def josephus(self, n, k):
		people = list(range(1, n + 1))
		idx = 0
		while len(people) > 1:
			idx = (idx + k - 1) % len(people)
			del people[idx]
		return people[0]


class Solution:

	def josephus(self, n, k):

		def rec(i, k, n, d, count):
			if i > n:
				i = i % n
			if count == 1:
				while d[i] != 1:
					i += 1
					if i > n:
						i = i % n
				return i
			temp = 0
			while temp != k:
				if d[i] == 1:
					temp += 1
				i += 1
				if i > n:
					i = i % n
			while d[i] != 1:
				i += 1
				if i > n:
					i = i % n
			d[i] = 0
			count -= 1
			val = rec(i + 1, k, n, d, count)
			return val
		d = {}
		for i in range(1, n + 1):
			d[i] = 1
		count = n
		val = rec(1, k - 1, n, d, count)
		return val


class Solution:

	def josephus(self, n, k):
		index = 0
		res = []
		arr = [i for i in range(1, n + 1)]

		def takej(n, k, arr, index, res, c):
			if len(arr) == 1:
				res = list(arr)
				return res
			if c >= k:
				return arr
			if c == k - 1:
				arr.pop(index)
				index = index % len(arr)
				c = 0
				l = takej(n, k, arr, index, res, c)
			l = takej(n, k, arr, (index + 1) % len(arr), res, c + 1)
			if len(l) == 1:
				res = l
			return res
		res = takej(n, k, arr, index, res, 0)
		return res[0]


class Solution:

	def josephus(self, n, k):
		return 1 + self.josephusHelper(n, k)

	def josephusHelper(self, n, k):
		if n == 1:
			return 0
		return (k + self.josephusHelper(n - 1, k)) % n


class Solution:

	def josephus(self, n, k):
		return self.remaining(n, k) + 1

	def remaining(self, n, k):
		if n == 1:
			return 0
		return (self.remaining(n - 1, k) + k) % n


class Solution:

	def josephus(self, n, k):
		list_of_elements = []
		for i in range(1, n + 1):
			list_of_elements.append(i)
		start = 0
		while len(list_of_elements) != 1:
			index_to_be_deleted = (start + k) % len(list_of_elements)
			if index_to_be_deleted == 0:
				start = 0
				list_of_elements.remove(list_of_elements[-1])
			else:
				start = index_to_be_deleted - 1
				list_of_elements.remove(list_of_elements[index_to_be_deleted - 1])
		return list_of_elements[-1]


class Solution:

	def josephus(self, n, k):
		v = 0
		for i in range(1, n):
			v = (v + k) % (i + 1)
		return v + 1


class Solution:

	def rec(self, li, k):
		if len(li) == 1:
			return li[0]
		t = k - 1
		while t >= len(li):
			t = t - len(li)
		li = li[t + 1:] + li[:t]
		return self.rec(li, k)

	def josephus(self, n, k):
		li = [i for i in range(1, n + 1)]
		return self.rec(li, k)


class Solution:

	def josephus(self, n, k):

		def help(n, k):
			if n == 1:
				return 0
			return (help(n - 1, k) + k) % n
		return help(n, k) + 1


class Solution:

	def josephus(self, n, k):
		if n == 1:
			return 1
		ans = self.josephus(n - 1, k)
		original = (ans + k) % n
		return original if original != 0 else n


class Solution:

	def josephus(self, n, k):

		def solve(start, arr, k, n):
			if len(arr) == 1:
				ans[0] = arr[0]
				return
			to_del_index = (start + k - 1) % n
			arr.pop(to_del_index)
			solve(to_del_index, arr, k, n - 1)
			return
		arr = [x for x in range(1, n + 1)]
		ans = [-1]
		solve(0, arr, k, n)
		return ans[0]


class Solution:

	def josephus(self, n, k):
		if n == 1:
			return 1
		survr = self.josephus(n - 1, k)
		survr_n = (survr + k - 1) % n + 1
		return survr_n


class Solution:

	def josephus(self, n, k, pos=[], start=0):
		if n == 1:
			if pos:
				return pos[0] + 1
			else:
				return 1
		if not pos:
			pos = [x for x in range(n)]
		i = (start + k - 1) % n
		pos.pop(i)
		return self.josephus(n - 1, k, pos, start=i % (n - 1))


def f(n, k):
	if n == 1:
		return 1
	return (f(n - 1, k) + k - 1) % n + 1

class Solution:

	def josephus(self, n, k):
		return f(n, k)


class Solution:

	def josephus(self, n, k):
		arr = [i + 1 for i in range(n)]
		return self.killer(arr, k, 0)

	def killer(self, arr, k, start):
		if len(arr) == 1:
			return arr[0]
		if start > len(arr) - 1:
			return self.killer(arr, k, 0)
		target = (start + (k - 1)) % len(arr)
		arr.pop(target)
		return self.killer(arr, k, target)


class Solution:

	def josephus(self, n, k):

		def f(a):
			if len(a) == 1:
				return a[0]
			if k <= len(a):
				s = k
			else:
				s = k % len(a)
				if s == 0:
					s = len(a)
			return f(a[s:] + a[:s - 1])
		return f(list(range(1, n + 1)))


class Solution:

	def josephus(self, n, k):
		a = []
		for i in range(n):
			a.append(i + 1)
		c = k - 1
		while len(a) != 1:
			if c > len(a) - 1:
				c = c % len(a)
			del a[c]
			c += k - 1
		return a[0]


class Solution:

	def josephus(self, n, k):
		arr = list(range(1, n + 1))
		while len(arr) > 1:
			i = k % len(arr)
			if i == 0:
				arr = arr[:-1]
			else:
				arr = arr[i:] + arr[:i - 1]
		return arr[0]


class Solution:

	def josephus(self, n, k):

		def fun(l, count, k, index):
			if len(l) == 1:
				return l[0]
			if count == k:
				l.pop(index)
				count = 0
				return fun(l, count + 1, k, index % len(l))
			else:
				return fun(l, count + 1, k, (index + 1) % len(l))
		l = []
		index = 0
		count = 1
		for i in range(1, n + 1):
			l.append(i)
		return fun(l, count, k, index)


class Solution:

	def jos(self, n, k):
		if n == 1:
			return 0
		return (self.jos(n - 1, k) + k) % n

	def josephus(self, n, k):
		return self.jos(n, k) + 1


class Solution:

	def josephus(self, n, k):
		l = []
		for i in range(n):
			l.append(i + 1)

		def ans(l, ind):
			ind = (ind + k - 1) % len(l)
			if len(l) == 1:
				return l[0]
			del l[ind]
			return ans(l, ind)
		return ans(l, 0)


class Solution:

	def josephus(self, n, k):
		arr = []
		for itr in range(1, n + 1):
			arr.append(itr)
		totalPerson = len(arr)
		toKill = k - 1
		currPerson = 0
		while totalPerson != 1:
			if toKill == 0:
				arr.pop(currPerson)
				totalPerson -= 1
				toKill = k - 1
			else:
				currPerson += 1
				toKill -= 1
			currPerson = currPerson % len(arr)
		return arr[currPerson]