June Long Challenge 2022 Solution

Divisible by i Solution Codechef

by

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:

Leave a Comment

8 + five =