The Hero Test-2

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
7 upvotes
Asked in company
Microsoft

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”
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1:

2
6 3
4 1

Sample Output 1:

4 2 1 3 6 5
2 4 3 1

Explanation of Sample Output 1:

Test Case 1:   There are 6 questions,the  and ninja will start solving the questions as shown in image below: 4 2 1 3 6 5


Test Case 2:   There are 4 questions, and ninja will start solving the questions as shown in the image below: 2, 4, 3, 1

Sample Input 2:

2
5 4
1 10

Sample Output 2:

5 1 3 4 2
1
Hint

Delete the element present at the Kth position.

Approaches (2)
Brute Force

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’.
Time Complexity

O(N ^ 2), where ‘N’ is the initial number of the questions given.

 

In the worst case, on removing each element, we need to make the whole array shift that will take O(N). Hence, the overall time complexity is O(N ^ 2).

Space Complexity

O(N), where ‘N’ is the initial number of questions given.

 

Storing of 1 to ‘N’ numbers will take O(N). Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
The Hero Test-2
Full screen
Console