Problems on Recursion
Wednesday, 21 May 2025 2:51 PM
Complexity Analysis of Recursive Solutions
K-th Symbol in Grammar.
Code :
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if n==1:
return 0
length=2**(n-1)
half=length//2
if k<=half :
return [Link](n-1,k)
else:
return 1 - [Link](n-1,k-half)
Question 2: Josephus problem: There are n friends that are playing a game. The friends are sitting in a circle and are numbered
from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n,
and moving clockwise from the nth friend brings you to the 1st friend.
The rules of the game are as follows:
[Link] at the 1st friend.
[Link] the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle
and may count some friends more than once.
[Link] last friend you counted leaves the circle and loses the game.
[Link] there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend
who just lost and repeat.
[Link], the last friend in the circle wins the game.
Given the number of friends, n, and an integer k, return the winner of the game.
Here is the thrilling story of Josephus:
The Josephus Problem is named after Flavius Josephus, a Jewish historian who lived during the 1st century. The
story behind this mathematical problem is quite dramatic. According to Josephus's account, during the Jewish-
Roman war, he and his 40 soldiers were trapped in a cave, surrounded by Roman forces. Preferring suicide to
capture, they decided to form a circle and proceed around it, systematically killing every third remaining person
until no one was left. Josephus, not wishing to die, quickly figured out where to position himself in the circle so
as to be the last survivor. He used this clever strategy to spare his own life, and then surrendered to the
Romans. This tale later inspired the Josephus Problem in mathematics, which explores the outcome of this
elimination process for different numbers of people and intervals.
as to be the last survivor. He used this clever strategy to spare his own life, and then surrendered to the
Romans. This tale later inspired the Josephus Problem in mathematics, which explores the outcome of this
elimination process for different numbers of people and intervals.
Code :
def findTheWinner(n, k):
#write code here LeetCode 1823
arr =[i+1 for i in range(n)]
def helper(arr,start_index):
if len(arr)==1:
return arr[0]
index_to_remove=(start_index+k-1)%len(arr)
del arr[index_to_remove]
return helper(arr,index_to_remove)
return helper(arr,0)
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
def helper(n):
if(n==1): return 0
return (helper(n-1)+k)%n
return helper(n)+1
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
winner=0
for i in range(2,n+1):
winner=(winner+k)%i
return winner+1