Last Updated: 25 Apr, 2021

The Hero Test-2

Moderate

Asked in company

Solve now

Problem statement

After passing hero test 1 with flying colours, now Ninja gets a different exam to get promoted to the hero class S.

Here also the pattern is the same as the previous exam, Ninja will get ‘N’ questions from 1 to ‘N’ but this time Ninja comes with a new technique to order the questions, he will solve a question after skipping ‘K’ questions (assume that after ‘N’th question he will come back to the first question) until he completes all questions.

Help Ninja by telling him the order of questions that is always a permutation of 1 to ‘N’.

For example:

If the number of questions is ‘5’ and ‘K’ = 3 
Then the order will be
 “4 3 5 2 1”

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of questions and number of questions that he wants to skip.

Output Format :

For each test case, return the order of the questions separated by space.

The output of each test case will be printed in a separate line.

Constraints :

1 <= T <= 5
1 <= N, K <= 3000

Where ‘T’ is the number of test cases, ‘N’ is the number of questions, and ‘K’ is the number of questions that Ninja will skip after solving one question.

Time limit: 1 second.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

The idea here is to remove the Kth element from the array. We need two operations to achieve this task, i.e. find the Kth element and delete that element, here we will do this by storing all numbers 1 to N in an array and then remove the Kth element.

Algorithm:

Declare an array ‘REM’ and ‘SOL’.
Store ‘1’ to ‘N’ in the ‘REM’ array.
Declare a variable ‘IND’ to store the current Index that will be deleted.
‘IND’ := ‘K’ % ‘N’.
Repeat the steps until ‘N’ > 0:
- ‘N’--
- sol.push(REM[IND])
- Remove element present at ‘IND’.
- If still ‘N’ is greater than 0:
  - ‘IND’ = (‘IND’ % ‘N’ + ‘K’) % ‘N’
Return ‘SOL’.

Solve now

02 Approach

The idea here is to use a policy-based data structure(PBDS), which you can read here. These data structures are designed for high-performance, flexibility, semantic safety, and conformance to the corresponding containers in std.

In this approach, we are going to optimise the previous approach using this data structure.

Using this DS, we can find the kth element and removal of element is done in logarithmic complexity.

Algorithm:

Declare an array ‘SOL’.
Declare a PBDS ‘INDEXEDSET’.
Store all integers from 1 to ‘N’ in the ‘INDEXEDSET’.
Declare a variable ‘IND’ : = K %N.
Repeat the steps until ‘N’ > 0:
- N--
- Declare and initialise an iterate ’IT’ := INDEXEDSET.find_by_order(IND).
- SOL.push(IT).
- After Removing IT from INDEXEDSET update IND as
  - IND := (IND % N + K ) %N
Return ‘SOL’.

Solve now