HackerRank : HourRank 18 – Where’s the Marble

By | March 2, 2017

Where’s the Marble Source : Hackerrank

Jill and Bob are playing the following game:

  • There are cups on saucers arranged in a straight line. Each saucer is numbered sequentially from to .
  • The game starts when Jill watches Bob place a marble inside the cup on saucer number .
  • Bob then takes turns. In each turn, he swaps the cups on a pair of saucers numbered and , where . The diagram below shows an example:

image

  • After Bob completes all his turns, Jill chooses an integer from to denoting the saucer where she think the cup with the marble is located.

Given and Bob’s sequence of moves, print the saucer number denoting the marble’s location at the end of the game.

Input Format

The first line contains two space-separated integers describing the respective values of (the marble’s initial location) and (Bob’s number of turns).
Each line of the subsequent lines contains two space-separated integers, and , describing the saucer numbers for the cups Bob swaps in his move.

Constraints

Output Format

Print an integer denoting the saucer number of the cup containing the marble at the end of the game.

Sample Input 0

5 3
2 5
7 10
2 9

Sample Output 0

9

Explanation 0

Bob places the marble in the cup on saucer and performs the following sequence of moves:

  1. imageSwap the cups in positions and , so the marble is now in the cup on saucer .
  2. imageSwap the cups in positions and ; neither of these cups currently contains the marble, so the marble is still in the cup on saucer .
  3. imageSwap the cups in positions and , so the marble is now in the cup on saucer .

image

Because the marble is in the cup on saucer at the end of the game, we print as our answer.

Solution

Since the no of cups are constant. We can use maps. As it wont take much memory here.
Initialized map with all zeros, and 1 at m position.

Run loop to all inputs and place conditions, if toPosition has marble., If fromPosition
has marble, or none of them have marble.
In the process, keep the position of marble in CurrentPosition variable.

Which is final output.