Problem of the day
Ninja wants the hero certificate to get the support of local police and government to help the people. But to get the hero certificate he needs to clear an exam.
The exam consists of ‘N’ questions from ‘1’ to ‘N’. To clear the exam Ninja needs to solve in a particular order. He needs to leave one question after solving one question(assume that after ‘N’th question he will come back to the first question). He will perform this action till all questions are solved. Help Ninja in exams by telling him the order.
For Example:If there are ‘5’ questions then the order will be:
“ 2 4 1 5 3 ”
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the number of questions.
Output Format :
For each test case, return the order of the questions separated by space.
The output for each test case is printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 5
1 <= N <= 3000
Where ‘T’ is the number of test cases, ‘N’ is the number of questions.
Time limit: 1 second.
2
6
4
2 4 6 3 1 5
2 4 3 1
Test Case 1:
There are 6 questions and the order is [2, 4, 6, 3, 1, 5]. Ninja will start solving the questions as shown in the image below:
Test Case 2:
There are 6 questions and the order is [2, 4, 3, 1]. Ninja will start solving the questions as shown in image below:
2
10
7
2 4 6 8 10 3 7 1 9 5
2 4 6 1 5 3 7
Try to maintain an array which tells about already solved questions.
The idea here is to implement the questions as it says because even in the worst case the constraints allow brute force solution.
We will maintain an array/list to check whether a particular question is solved or not.
Algorithm:
Description of ‘findNext’ function.
This function will take three parameters :
int findNext(VIS, I, N):
O(N * log(N)), where ‘N’ is the number of questions.
As we need to iterate the whole array log(N) number of times because in the first iteration we will cover N/2 elements then N/4, N/8 …. and so on. So in the log(N) iteration of the array we will get all the numbers from ‘1’ to ‘N’. Hence, the overall time complexity is O(N * log(N)).
O(N), where ‘N’ is the number of questions.
We are storing ‘N’ elements to check whether they have been visited or not. Hence, the overall space complexity is O(N).