# Divisible by i Solution Codechef

## Divisible by i Solution Codechef

You are given an integer N. Construct a permutation P of length N such that For all i (1≤iN-1), i divides abs(Pi+1​−Pi). Recall that a permutation of length N is an array where every integer from 1 to N occurs exactly once. It can be proven that for the given constraints at least one such P always exists.

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow.
• The only line of each test case contains an integer N – the length of the array to be constructed.

Output Format

• For each test case, output a single line containing N space-separated integers P1​,P2​,…,PN, denoting the elements of the array P.
• If there exist multiple such arrays, print any.

Constraints

• 1≤T≤5⋅104
• 2≤N≤105
• The sum of N over all test cases does not exceed 105.

Sample 1:

Input

```2
2
3
```

Output

```1 2
2 1 3
```

Explanation:

Test case 1: A possible array satisfying all the conditions is [1,2]:

• For i=1: abs(A2−A1​)=abs(2-1)=1 is divisible by 1.

Test case 2: A possible array satisfying all the conditions is [2,1,3]:

• For i=1: abs(A2A1​)=abs(1-2)=1 is divisible by 1.
• For i=2: abs(A3A2​)=abs(3-1)=2 is divisible by 2.

### SOLUTION

Program: Divisible by i Solution in Python

``````for _ in range(int(input())):
n = int(input())
p = [n]
m = n
for i in range(n-1,0,-1):
el = p-i
if 1<=el and el<=m and el not in p:
p.insert(0,el)
else:
p.insert(0,p+i)
for i in p:
print(i, end=' ')
print()``````

Program: Divisible by i Solution in C++

``````#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
int k=0;
int e =n;
int s =1;
for(int i=n-1;i>=0;i--){
if(k==0){
arr[i]= e;
e--;
k=1;
}
else if(k==1){
arr[i]=s;
s++;
k=0;
}
}

for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
return 0;
}``````

Program: Divisible by i Solution in Java

``````import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc= new Scanner(System.in);

int t=sc.nextInt();

while(t-->0)
{
int num=sc.nextInt();

int n=num;
int a[]= new int[n];
a[n-1]=n;

int counter=0;
int k=n-1;

for(int i=n-2;i>=0;i--)
{
if(counter%2==0)
{
a[i]=n-k;
n-=k;
}
else
{
a[i]=n+k;
n+=k;
}
k-=1;
counter+=1;
}

for(int i=0;i<num;i++)
System.out.print(a[i]+" ");
System.out.println();
}
}
}``````

Related: