Interview Questions/Coding/K-th Eliminated Child in a Circle

K-th Eliminated Child in a Circle

Preview mode. Log in to edit, run, submit, and save progress.

Medium

K-th Eliminated Child in a Circle

Consider a game where there are n children (numbered 1,2,.....,n) in a circle. During the game, every second child is removed from the circle, until there are no children left. Your task is to process q queries of the form: "when there are n children, who is the kth child that will be removed?" Input Format: The first line contains an integer q - the number of queries. Each of the next q lines contains two integers: n - the number of children in the circle. k - the position in the elimination order to find. Output Format: For each query, print a single integer representing the label of the k-th child removed from the circle.

Examples

Example 1

Input:

1
7  1

Output:

Explanation: For n = 7, the removal order is: 2 4 6 1 5 3 7 The 1st removed child is 2.

Approach hint

Start with the simplest clear approach, explain the trade-off, then move toward the cleaner answer.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp