Josephus Problem in O(1) Time

Problem Statement :

INITIAL STATE
state after the game operations
o/p for different values of n

Initial intuition : If n is a power of 2, in that case, person who will survive will be person who starts the game.

Hence from the above proof, we can take as chair numbered c = f(n) = 2*p+1, where n = 2^K +p. This formula can be used to solve the problem in constant time.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Shiwani Sinha 🍁

Shiwani Sinha 🍁

81 Followers

💻| Software Engineer @microsoft 🧋| Fuelled by Caffeine ❤️