Dynamic programming or Mathematics | Josephus Problem

I am facing this issue from the long back. Its not exactly issue, its may be i need more practice. Need your help on this.

Sometimes, I came across with few problems which seems can be solved mathematically. I invest more work on coming up with some maths solution but fails. May be its more hard mathematically but most of the times that problem can’t be solved using maths rather generally dynamic programming or some other algorithmmic approach.
So, My question is, How or what can be that distinction or say argument such that I can arrive at the conclusion at the earlist that we can’t solve the current problem using only maths.

Take example like Josephus problem(https://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution)

After reading the problem, I can think like there is a circular array present and given some constant value of k. We need to remove the first element in each consecutive elements of set k(or something like this). Seems like some mathematically pattern may exist right. like use of some modulus which may give us some reminder or something along that line. I will start invest more time in finding out this and bam times up.

Upon looking into the solution, its dp. (which makes sense after knowing that its dp).

How would you approach this problem, and get to know that we can’t solve it mathematically at the earliest.

1 Like

watch this video it may help you in Josephus problem when we have to kill alternate person.

Thanks, exactly what I was looking for. Seems like it should be hit and try first, (see pattern) if can’t able to find -> must be dp or something else.

agree.