Techgig July contest : Musical Pillow : Level (Medium)

Problem Statement

In a family party, people are playing the musical pillow game in which people sit in a circle. Starting from the first person, they transfer the pillow to the person to their left. For simplicity, we’ll assume that people are assigned an integer tag from 1 to n(which is the total number of people) in the clockwise manner, so that during the game pillow is passed in the increasing sequence of. When game starts, a song is played and the person with the pillow at the end of the song, is eliminated and game starts again till there is only one person is left, which is declared as the winner of the game.

                                                You are give total number of people playing the game and the duration of the song in seconds. If game starts with pillow being put on a table & person1 (person with tag number 1)picking it up(at the end of first second [time], pillow will be with person1) and each person takes one second to transfer the pillow to the next person, you have to tell which person (tag number) which will win the game.

Examples

Example 1: Let there are 5 people and duration of the song is 2 seconds(every second person present in the clockwise manner will be eliminated) then people will be eliminated in the following order: 2,4,1, 5 and person with tag 3 will be the winner.

Example 2: If there are 11 people in the beginning of the game, and song duration is 4 seconds then people will be eliminated in following order: 4,8,1,6,11, 7, 3,2,5, 10 and winner will be the person with tag no. 9.

==============================================================================

Dont know why they called it as a medium level problem after that Bitonic problem (Easy level) which ruined a couple of days of my life.. :(

Lets come to the problem, its a very easy problem to solve. A new programmer would face only one problem i.e to start the loop from first position when we reach the end of our sequence.

Here`s the logic :

i) First we declare an array with the number of persons (input1) and fill it with 0.

ii) Then, as the games starts and a person gets out, that position is to be marked as 1. Because while the next round this position needs to be ignored as the person is already out.

ii) Continue till only a single person remains.

The tricky point here is, how to traverse through the loop. The answer to this is, just maintain a flag which is updated only when we encounter a 0 at that position in the array else just move on until flag becomes equal to input2. In case, we reach the end of array, start from 1 again without resetting the flag.

If you have doubts or you want the source code for reference the comment below with your email address.

EDIT: Just learnt to find that this is called as "Josephus Problem" and a recursive solution can be written for it.