Page Contents
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:
- Subscriptions Solution Codechef
- Alternate Additions Solution Codechef
- Equal Strings Solution Codechef
- Divisible by i Solution Codechef
- Possible GCD Solution Codechef
- Expected move Solution Codechef
- Reduce to zero Solution Codechef
- Full Path Eraser Solution Codechef