There are n people standing in a circle (numbered clockwise 1 to n) waiting to be executed. The counting begins at point 1 in the circle and proceeds around the circle in a fixed direction (clockwise). In each step, a certain number of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom.
Given the total number of persons n and a number k which indicates that k-1 persons are skipped and k^{th} person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive.
Example 1:
Input:
n = 2, k = 1
Output:
2
Explanation:
Here, n = 2 and k = 1, then safe position is
2 as the person at 1st position will be killed.
Example 2:
Input:
n = 4, k = 2
Output:
1
Explanation:
The safe position is 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function safePos() which takes an Integer n as input and returns the safe position.
Expected Time Complexity: O(n*n)
Expected Auxiliary Space: O(n)
Follow up: This problem can be solved in linear time. Can you come up with a solution?
Constraints:
1 <= n,k <= 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Complete search

Starter code: #User function Template for python3



class Solution:

    def safePos(self, n, k):

        # code here 

Solutions:
class Solution:

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


class Solution:

	def alivePerson(self, persons, k, start):
		if len(persons) == 1:
			return persons[0]
		dead_index = (start + k - 1) % len(persons)
		start = dead_index
		persons.pop(dead_index)
		return self.alivePerson(persons, k, start)

	def safePos(self, n, k):
		persons = []
		for i in range(1, n + 1):
			persons.append(i)
		start = 0
		return self.alivePerson(persons, k, start)


class Solution:

	def solve(self, arr, k, i):
		if len(arr) == 1:
			return arr[0]
		else:
			i = (i + k) % len(arr)
			arr.pop(i)
			self.solve(arr, k, i)

	def safePos(self, n, k):
		arr = list(range(1, n + 1))
		i = 0
		self.solve(arr, k - 1, i)
		return arr[0]


class Solution:

	def safePos(self, n, k):
		arr = []
		for i in range(0, n):
			arr.append(i)
		i = 0
		while n > 1:
			r = (i + k - 1) % n
			arr.remove(arr[r])
			n = n - 1
			if r == n:
				i = 0
			i = r
		return arr[0] + 1


class Solution:

	def safePos(self, n, k):
		alive = list((i for i in range(1, n + 1)))

		def killing(ind, n):
			if n == 1:
				return alive[0]
			ind = (ind + k - 1) % n
			x = alive.pop(ind)
			return killing(ind, n - 1)
		return killing(0, n)


class Solution:

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


class Solution:

	def safePos(self, n, k):
		cnt = n
		arr = [i + 1 for i in range(n)]
		prev = 0
		i = 0
		while len(arr) > 1:
			N = len(arr)
			i = (i + (k - 1)) % N
			arr.pop(i)
			i = i % (N - 1)
		return arr[i]


def rec(i, k, arr):
	if len(arr) == 1:
		return
	i = (i + k - 1) % len(arr)
	arr.pop(i)
	rec(i, k, arr)

class Solution:

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


class Solution:

	def safePos(self, n, k):
		res = self.dummy(n, k)
		return res + 1

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


class Solution:

	def safePos(self, n, k):
		sp = 1
		for i in range(2, n + 1):
			sp = (sp + k - 1) % i + 1
		return sp


class Solution:

	def safePos(self, n, k):
		circle = list(range(1, n + 1))
		current = 0
		eliminated = []
		while len(circle) > 1:
			current = (current + k - 1) % len(circle)
			eliminated.append(circle.pop(current))
		return circle[0]


class Solution:

	def safePos(self, n, k):
		soldiers = list(range(1, n + 1))
		index = 0
		ans = -1
		res = self.solve(soldiers, k, index, ans)
		return res

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


class Solution:

	def safePos(self, n, k):
		ans = list((i + 1 for i in range(n)))
		start = 0
		while len(ans) > 1:
			start = (start + k - 1) % len(ans)
			ans.pop(start)
		return ans[0]


class Solution:

	def safePos(self, n, k):
		return 1 + self.safePosHelper(n, k)

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


class Solution:

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

		def helper(ar, index, z):
			if len(ar) == 1:
				return
			index = (index + z) % len(ar)
			ar.pop(index)
			helper(ar, index, z)
			return
		helper(arr, 0, k - 1)
		return arr[0]


class Solution:

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


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

class Solution:

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


class Solution:

	def safePos(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 safePos(self, n, k):
		person = []
		index = 0
		k -= 1
		for i in range(1, n + 1):
			person.append(i)

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


class Solution:

	def safePos(self, n, k):
		if n == 1:
			return 1
		killed = list(range(1, n + 1))
		start = 0
		for i in range(n - 1):
			next_to_die = (start + k - 1) % (n - i)
			killed.pop(next_to_die)
			start = next_to_die % (n - i - 1)
		return killed[0]


class Solution:

	def safePos(self, n, k):
		n_pos = list(map(lambda x: x, range(1, n + 1)))
		i = 0
		const_k = k
		while len(n_pos) > 1:
			k = const_k
			while k > len(n_pos):
				k = k - len(n_pos)
			i += k - 1
			diff = i - len(n_pos)
			if diff >= 0:
				i = diff
			n_pos.pop(i)
		return n_pos[0]


class Solution:

	def safePos(self, n, k):
		arr = [i + 1 for i in range(n)]
		x = (k - 1) % len(arr)
		while len(arr) != 1:
			arr.pop(x)
			if x + k - 1 < len(arr):
				x = x + k - 1
			else:
				x = (x + k - 1) % len(arr)
		return arr.pop()


class Solution:

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

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


class Solution:

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


class Solution:

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

	def safePos(self, n, k):
		j = self.solve(n, k)
		return j


class Solution:

	def safePos(self, n, k):
		person = []
		for i in range(0, n):
			person.append(i + 1)
		n1 = n
		pos = 0
		while n1 != 1:
			pos = (pos + k - 1) % n1
			person.pop(pos)
			n1 -= 1
		return person[0]


class Solution:

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

		def fun(l, k, ci):
			if len(l) == 1:
				return l[0]
			ci = (ci + k) % len(l)
			return fun(l[:ci] + l[ci + 1:], k, ci)
		return fun(l, k - 1, 0)


class Solution:

	def safePos(self, n, k):
		arr = []
		for i in range(1, n + 1):
			arr.append(i)
		idx = 0
		return self.solve(arr, k, idx, len(arr))

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


class Solution:

	def safePos(self, n, k):

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


class Solution:

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

	def solution(self, arr, k, res):
		if len(arr) == 1:
			return arr[0]
		res = (res + k - 1) % len(arr)
		arr.remove(arr[res])
		return self.solution(arr, k, res)


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

class Solution:

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


class Solution:

	def safePos(self, n, k):
		arr = [i for i in range(1, n + 1)]
		k -= 1
		index = 0
		while len(arr) != 1:
			index = (index + k) % len(arr)
			arr.pop(index)
		return arr[0]


class Solution:

	def safePos(self, n, k):

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


class Solution:

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

		def remove(arr, i, k):
			if len(arr) == 1:
				return arr[0]
			i = (i + k - 1) % len(arr)
			del arr[i]
			return remove(arr, i, k)
		ans = remove(arr, 0, k)
		return ans


from collections import defaultdict

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

class Solution:

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


class Solution:

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

		def solve(ls, i, k):
			if len(ls) == 1:
				return
			i = (i + k) % len(ls)
			del ls[i]
			solve(ls, i, k)
		solve(ls, 0, k - 1)
		return ls[0]


import collections

class Solution:

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


class Solution:

	def safePos(self, n, k):
		if k == 1:
			return n
		arr = [i for i in range(1, n + 1)]
		pos = 0
		while n > 1:
			pos = (pos + k - 1) % n
			arr.pop(pos)
			n -= 1
			pos = pos % n
		return arr[0]


class Solution:

	def safePos(self, n, k):

		def solve(vec, k, idx, ans):
			if len(vec) == 1:
				return
			idx = (idx + k) % len(vec)
			vec.remove(vec[idx])
			solve(vec, k, idx, ans)
		vec = [-1] * n
		for i in range(1, n + 1):
			vec[i - 1] = i
		k = k - 1
		idx = 0
		ans = -1
		solve(vec, k, idx, ans)
		return vec[0]


class Solution:

	def solve(self, v, k, idx):
		if len(v) == 1:
			return v[0]
		idx = (idx + k) % len(v)
		v.remove(v[idx])
		return self.solve(v, k, idx)

	def safePos(self, n, k):
		v = list(range(1, n + 1))
		k -= 1
		idx = 0
		return self.solve(v, k, idx)


class Solution:

	def safePos(self, n, k):
		p = list(range(1, n + 1))

		def executioner(k, s):
			if len(p) == 1:
				return
			d = (s + k) % len(p)
			p.pop(d)
			executioner(k, d)
		executioner(k - 1, 0)
		return p[0]


class Solution:

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

	def safePos(self, n, k):
		li = [int(x) for x in range(0, n)]
		knif_position = 0
		while len(li) > 1:
			position_to_kill = knif_position + (k - 1)
			position_to_kill %= len(li)
			li.pop(position_to_kill)
			knif_position = position_to_kill
		return li[0] + 1


class Solution:

	def safePos(self, n, k):
		k = k - 1
		ans = []
		array = []
		for i in range(0, n):
			array.append(i + 1)

		def solve(array, index):
			if len(array) == 1:
				ans.append(array[0])
				return None
			index = (index + k) % len(array)
			del array[index]
			solve(array, index)
		solve(array, 0)
		return ans[0]


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

class Solution:

	def safePos(self, n, k):
		return safe(n, k) + 1


class Solution:

	def safePos(self, n, k):
		arr = [x for x in range(1, n + 1)]
		ans = []
		tempK = k - 1
		tempInd = 0
		self.logic(tempK, tempInd, ans, arr)
		return ans[0]

	def logic(self, k, ind, ans, arr):
		if len(arr) == 1:
			ans.append(arr[0])
			return
		temp = (ind + k) % len(arr)
		arr.remove(arr[temp])
		self.logic(k, temp, ans, arr)


class Solution:

	def execute(self, arr, k, indx):
		if len(arr) == 1:
			return arr[0]
		indx = (indx + k) % len(arr)
		arr.pop(indx)
		x = Solution.execute(self, arr, k, indx)
		return x

	def safePos(self, n, k):
		arr = []
		for i in range(1, n + 1):
			arr.append(i)
		x = Solution.execute(self, arr, k - 1, 0)
		return x


class Solution:

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

		def sol(index, arr, k):
			if len(arr) == 1:
				return arr[0]
			index = (index + k) % len(arr)
			del arr[index]
			return sol(index, arr, k)
		return sol(0, v, k - 1)


class Solution:

	def safePos(self, n, k):

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


class Solution:

	def safePos(self, n, k):
		list1 = []
		for i in range(1, n + 1):
			list1.append(i)
		i = 0
		while len(list1) != 1:
			index = (i + k - 1) % len(list1)
			x = list1.pop(index)
			i = index
			if i > len(list1):
				i = 0
		return list1[0]


class Solution:

	def safePos(self, n, k):
		arr = [None] * n
		for i in range(n):
			arr[i] = i
		i = 0
		while 1:
			if n == 1:
				break
			else:
				arr.remove(arr[(i + k - 1) % n])
				i = (i + k - 1) % n
				n -= 1
		return arr[0] + 1


class Solution:

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

		def fun(n, k, nextindex):
			if n == 1:
				return arr[0]
			else:
				n -= 1
				nextindex = (nextindex + k - 1) % len(arr)
				arr.pop(nextindex)
				return fun(n, k, nextindex)
		return fun(n, k, 0)


class Solution:

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

	def safePos(self, n, k):
		re = self.helper(n, k)
		return re