Problem

In the Jay’s game tournament, N players compete in a knockout format. Each player is sequentially assigned a number from 1 to N. The matches are arranged as 1 vs 2, 3 vs 4, …, N-1 vs N. The winner of each game advances to the next round, where they receive new sequential numbers starting from 1 for the advancing players. For instance, if player 2 beats player 1, in the next round, they receive number 1, and so on until only one player remains.

Given the number of participants N, and two specific participants A and B, you need to determine in which round players A and B will meet, assuming both players always win until they meet each other.

Constraints

• N is a natural number between 21 and 220, and it’s always a power of two, so no byes occur in the tournament.
• A and B are natural numbers less than or equal to N (A ≠ B).

Example

Explanation of Example

• First Round:

  • Player 4 competes against player 3, and player 7 competes against player 8. Assuming both win, player 4 becomes number 2 in the next round, and player 7 becomes number 4.

• Second Round:

  • Player 2 (formerly player 4) now competes against player 1, and player 4 (formerly player 7) competes against player 3. Both win again.

• Third Round:

  • Players 1 and 2 meet, where player 1 is the former player 2, and player 2 is the former player 4. Since these are the new identities of players 4 and 7, they meet in this round.

Therefore, players A (4) and B (7) meet in the third round, hence the answer is 3.

How to approach?

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int solution(int n, int a, int b) {
        int round = 0;
        
        while (a != b) {
            a = (a + 1) / 2;
            b = (b + 1) / 2;
            round++;
        }
        
        return round;
    }
}