Divisible by i Solution Codechef
You are given an integer N. Construct a permutation P of length N such that For all i (1≤i≤N-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(A2−A1)=abs(1-2)=1 is divisible by 1.
- For i=2: abs(A3−A2)=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[0]-i
if 1<=el and el<=m and el not in p:
p.insert(0,el)
else:
p.insert(0,p[0]+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: