The Hero Test - 1

Easy
0/40
Average time to solve is 15m
profile
Contributed by
49 upvotes
Asked in companies
InfosysNagarro Software

Problem statement

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 ”
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 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.
Constraints :
1 <= T <= 5
1 <= N <= 3000

Where ‘T’ is the number of test cases, ‘N’ is the number of questions.

Time limit: 1 second.

Sample Input 1:

2
6
4      

Sample Output 1:

2 4 6 3 1 5
2 4 3 1

Explanation of Sample Output 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: 

Sample Input 2:

2
10 
7

Sample Output 2:

2 4 6 8 10 3 7 1 9 5 
2 4 6 1 5 3 7 
Hint

Try to maintain an array which tells about already solved questions.

Approaches (1)
Brute Force

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:

  • Declare an array ‘VIS’ of size ‘N’ initialized with ‘0’.
  • Declare two integers ‘V’ := 0 and ‘I’ := 1.
  • Repeat the steps until ‘V’ < ‘N’
    • ‘I’ := findNext(‘VIS’, ‘I’, ‘N’)
    • ‘I’ ++
    • ‘I’ %= ‘N’
    • If(‘I’ == 0)
      • ‘I’ = ‘N’.
    • ‘SOL’.push(‘I’)
    • VIS[‘I’] = 1.
    • ‘V’++
  • Return ‘SOL’.

 

Description of ‘findNext’ function.

 

This function will take three parameters :

  • ‘I’: An integer to keep track of the current index of the array.
  • ‘N’: An integer denoting the total numbers of elements.
  • ‘VIS’: An array ‘VIS’ to check whether a number is already visited or not.

int findNext(VIS, I, N):

  • Repeat the steps until VIS[I] != 0
    • I++
    • I %= N
    • If( I == 0)
      • I = N
  • Return I.
Time Complexity

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)).

Space Complexity

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).

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