I could do the queue, but couldn't think of the recursive solution. I was looking at soo many TH-cam videos trying to explain this Josephus problem, but none of them could show the intuition. You are the only one who showed how the recursive logic worked, and how we can take a step from queue logic to the recursive one. Thank you so much!!
I think u did a great job explaining it! The way that help me understand the subproblems was by visualizing like this " n = 5 k = 2 f(n) = [1, 2, 3, 4, 5] f(n - 1) = [3, 4, 5, 1] f(n - 2) = [5, 1, 3] f(n - 3) = [3, 5] f(n - 4) = [3] " its similar to how you did except, instead of appending the nums, each function call can be viewed as its own list, where each i = 0 is the prev k + 1, thus the relation f(n) = (f(n - 1) + k) % n, can be seen (where f(n) is the index of the correct person in the current list). But jeez, this problem was pretty crazy. It's also cool that we never care about which person that have to leave, bc we know that the basecase person will be safe and we only recover its original index, Great video!!
I was asked this in Splunk OA and I solved it with queue logic. Didn't hear back from them so some people might have solved with the recursive intuition I bet.
I had to watch the 2nd approach twice to understand. It's just the shifting of indices is new to me and I was concentrating solely on that rather than overall solution. Sidenote: This might be obvious to some or completely irrelevant to others. I was wondering what might be the usecase for this crazy solution. There might be a better one (let me know if there is), but to my surprise I found it in "hide and seek" game. There are many ways to determine who is the seeker. One of those is by counting using set of phrases (this will differ most likely, but we used "inky pinky ponky" if that rings a bell to few of you). So there is a solution for that mini-game. After finding out the usecase, I checked the title of the problem and thought this might be reference for the problem.
A Very simple code in python class Solution: def findTheWinner(self, n: int, k: int) -> int: queue = deque(list(range(1, n + 1))) while len(queue) > 1: queue.rotate(-k) queue.pop() return queue[0]
NGL, i code my solutions in C++ just bcoz i started that way, even though i am fluent with python as well. but when i first saw deque approach i was kind disheartened to see that, coz in the solutions board, everyone was using that recursive approach, and i thought that you were using different approach, so i started for looking at other videos, and they were really not doing a good job at explaining it, and when i thought that it doesnt matter if your solution is not the one i was looking for, but atleast i am able to understand its intuition well, you came up with the recursive approach later in the video, so what i am trying to say is, you explained it well. TLDR: you explained it well and next time just tell at the start of video that you have more than one solution, ik you always do that, but i am not used to it T_T. thanks btw.
Linked list solution JS var findTheWinner = function (n, k) { function ListNode(val, next) { this.val = (val === undefined ? 0 : val) this.next = (next === undefined ? null : next) } let head = new ListNode(1) let prev = head for (let i = 2; i
You did good while explaining the recursive and bottom up approach, but it's still difficult to wrap my head into the solution. I could do the Queue though.
Am I understand right that in recursion we create an arr= list(range(1, n + 1)) and in function we pop k - 1 and solve subproblem (arr). When the length of arr is 1 return arr[0]?
I did this iteratively (using array) and then optimized it using queue. (Looking at the constraints, I knew these would pass) Could not at all come up with the recursive approach.
My code i took me 2 hours to come up with class Solution: def findTheWinner(self, n: int, k: int) -> int: players = [i for i in range(1, n + 1)] length = len(players) i = 0 while length != 1: i = (i + k - 1) % length players.pop(i) length -= 1 return players[0]
ur explanation is great. regarding other resources, I found this one to be helpful. th-cam.com/video/8uFWG6xfkuc/w-d-xo.html not that it is better than yours but a helpful compliment to understanding the whole concept better. I couldn't understand his until I watched yours, and I couldn't understand yours without watching his. I really appreciate your work. All the best.
I could do the queue, but couldn't think of the recursive solution.
I was looking at soo many TH-cam videos trying to explain this Josephus problem, but none of them could show the intuition.
You are the only one who showed how the recursive logic worked, and how we can take a step from queue logic to the recursive one.
Thank you so much!!
thank you my bro!
I had no clue why the modulo solutions worked until watching this video, now it makes perfect sense. Thank you.
Sometimes it’s hard to wrap my head around recursive solutions but you explained it so perfect and clear! Thank you!
u explained the recursive approach fast and properly, just what i needed
Greatest explanation ever. Not everyone will have such skills. I really appreciate you choosing this as a career. Thank you for changing lives!
I think u did a great job explaining it!
The way that help me understand the subproblems was by visualizing like this
"
n = 5
k = 2
f(n) = [1, 2, 3, 4, 5]
f(n - 1) = [3, 4, 5, 1]
f(n - 2) = [5, 1, 3]
f(n - 3) = [3, 5]
f(n - 4) = [3]
"
its similar to how you did except, instead of appending the nums, each function call can be viewed as its own list, where each i = 0 is the prev k + 1, thus the relation f(n) = (f(n - 1) + k) % n, can be seen (where f(n) is the index of the correct person in the current list). But jeez, this problem was pretty crazy.
It's also cool that we never care about which person that have to leave, bc we know that the basecase person will be safe and we only recover its original index,
Great video!!
So much clearer now! You did a great job explaining this question. Love your videos!
Would you ask this in an interview? Till what level of optimization would you expect the candidate to solve?
definitely not, if you do it's unlucky, like 0.1% unlucky. the queue solution is approachable with hints but not the recursive one imo
Fml. I got determine the winner of Babylon problem if all players play optimally in an interview.
I was asked this in Splunk OA and I solved it with queue logic. Didn't hear back from them so some people might have solved with the recursive intuition I bet.
@@patelvrukshal5102 that sucks. don't think its possible to come up with that approach in an interview unless you have seen it before
I had to watch the 2nd approach twice to understand. It's just the shifting of indices is new to me and I was concentrating solely on that rather than overall solution.
Sidenote: This might be obvious to some or completely irrelevant to others. I was wondering what might be the usecase for this crazy solution. There might be a better one (let me know if there is), but to my surprise I found it in "hide and seek" game. There are many ways to determine who is the seeker. One of those is by counting using set of phrases (this will differ most likely, but we used "inky pinky ponky" if that rings a bell to few of you). So there is a solution for that mini-game. After finding out the usecase, I checked the title of the problem and thought this might be reference for the problem.
Thank you so much ! All 3 explanations were great
A Very simple code in python
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
queue = deque(list(range(1, n + 1)))
while len(queue) > 1:
queue.rotate(-k)
queue.pop()
return queue[0]
Thank you so much
was not able to have the queue neuron fire today. I was having trouble trying to represent the problem
NGL, i code my solutions in C++ just bcoz i started that way, even though i am fluent with python as well.
but when i first saw deque approach i was kind disheartened to see that, coz in the solutions board, everyone was using that recursive approach, and i thought that you were using different approach, so i started for looking at other videos, and they were really not doing a good job at explaining it, and when i thought that it doesnt matter if your solution is not the one i was looking for, but atleast i am able to understand its intuition well, you came up with the recursive approach later in the video, so what i am trying to say is, you explained it well.
TLDR: you explained it well and next time just tell at the start of video that you have more than one solution, ik you always do that, but i am not used to it T_T.
thanks btw.
Linked list solution JS
var findTheWinner = function (n, k) {
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
let head = new ListNode(1)
let prev = head
for (let i = 2; i
you did a good job explaining last approach broski
for the iterative one you can start from 2 since everything %1 is 0 (of course, doesn't really matter the time consumed is insignificant)
You did good while explaining the recursive and bottom up approach, but it's still difficult to wrap my head into the solution. I could do the Queue though.
very good explanation
26 seconds ago is amazing
Thank you so much! This one is greatly helpful!
I have been thinking "why gpt said adding k is for adjustment??" for 2 days and got nothing done😂
simply Genius
coming with A solution is good, but blud has 2 3 solutions up his sleeve, straight up monster
Am I understand right that in recursion we create an arr= list(range(1, n + 1)) and in function we pop k - 1 and solve subproblem (arr).
When the length of arr is 1 return arr[0]?
It was great !
I did this iteratively (using array) and then optimized it using queue. (Looking at the constraints, I knew these would pass)
Could not at all come up with the recursive approach.
My code i took me 2 hours to come up with
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
players = [i for i in range(1, n + 1)]
length = len(players)
i = 0
while length != 1:
i = (i + k - 1) % length
players.pop(i)
length -= 1
return players[0]
i think the iterative version is a bit more inuitive than the recursive one
Simulation is easy to come up with but recursive is 🔥🔥
Tried to code up wikipedia's general formula and it looks like invalid
einstein wouldnt waste a millisecond of his life solving leetcode sadly 😭
you never know, he loved day dreaming and solving hard problems by running thought experiments in his head
Why not just use a linked list?
Even the hints just tell you to simulate maaaan 😭 what is this question?
ur explanation is great.
regarding other resources, I found this one to be helpful.
th-cam.com/video/8uFWG6xfkuc/w-d-xo.html
not that it is better than yours but a helpful compliment to understanding the whole concept better.
I couldn't understand his until I watched yours, and I couldn't understand yours without watching his.
I really appreciate your work.
All the best.
I suspect there is a clever O(1) time and O(1) space solution. I haven't figured out such a solution yet but my gut tells me there might be one.
there is
th-cam.com/video/uCsD3ZGzMgE/w-d-xo.html
There is
there is for fixed size values of k: en.wikipedia.org/wiki/Josephus_problem
just for k = 2 and k = 3, people discovered.
class Solution:
def findTheWinner(self, n: int, k: int) -> int:
s=0
total=n*(n+1)//2
l=list(range(1,n+1))
i=0
while len(l)!=1:
if i+k-1>=n:
i=((i+k-1)%n)
else:
i+=k-1
print(l,i)
s+=l.pop(i)
n-=1
return total-s
no queue,simple list
Still space: O(n)