Smallest lexicographical permutation such that a[i] % i is equal to 0
Given the integers N and X, the task is to find the smallest lexicographical permutation a[], using all integers [1, N] such that a[i]%i is equal to 0 given that the a[1] = X (the first element of permutation) and a[N] = 1 (the last element of permutation) which means a[1], a[N] are constants and the elements from indices [2, N – 1] should follow a[i] % i = 0.
Note: Follow 1-based indexing
Examples:
Input: N = 4, X = 2
Output: 2 4 3 1
Explanation: The a[1] = 2, a[4] = 1 and a[2]%2, a[3]%3 is equal to 0 so the given condition as per question is satisfied and it is the smallest lexicographical permutation.Input: N = 5, X = 4
Output: -1
Explanation: There is no such possible permutation that satisfies the given condition.
Approach: To solve the problem follow the below approach:
The approach is based on the logic that out of integers of permutation from 1 to N, 1 and X are placed and the Xth indexed position should be replaced by smallest multiple of X. Hashing is used to check whether any number to be placed at ith position is already used or not.
Follow the steps mentioned below to solve the problem:
- Initialize the check[] array to check whether the element to be placed at the ith index is visited or not.
- Initialize vector permutation to store the final result permutation.
- Initialize a flag variable to check if there is a possibility to form a permutation.
- As given in the question, mark 1 and x as visited as they are placed.
- Traverse from 2 till N
- Now, check for the number to be placed at ith position to satisfy the condition. Iterate from j = i to all multiples of j to place the lowest possible multiple.
- If the element itself is not visited already then place it.
- Else, check for a multiple that is not visited and divides N.
- If the ith indexed element is still -1 we are unable to find an element to place so mark the flag and break.
- Print -1 if not possible to form a permutation
- Print the permutation if it is possible to form a permutation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to build the permutation void buildpermutation( int n, int x) { // Initialize the check[] array to // check whether the element to be // place at i th index is visited or not. bool check[n + 1] = { 0 }; // Initialize vector permutation to // store the final result permutation vector< int > permutation(n + 1, -1); // Initialize a flag variable to check // if there is a possibility // to form a permutation int flag = 0; int i = 0; // As given in the question permutation[1] = x; permutation[n] = 1; // Mark 1 and x as visited as // they are placed check[1] = true ; check[x] = true ; // Traverse from 2 till n for (i = 2; i < n; i++) { // Now check for the number to be // placed at ith position to satisfy // the condition. Iterate from j = i // to all multiples of j to place // the lowest possible multiple for ( int j = i; j <= n; j += i) { // If the element itself is not // visited already the place it if (check[j] == false && i == j) { permutation[i] = j; check[j] = true ; break ; } // Else check for a multiple // which is not visited and // divides n else if (check[j] == false && (n % j) == 0) { permutation[i] = j; check[j] = true ; break ; } } // If the ith indexed element is // still -1 we are unable to find // an element to place so mark the // flag and break. if (permutation[i] == -1) { flag++; break ; } } // Return -1 if not possible to // form a permutation if (flag > 0) { cout << -1 << endl; return ; } else { // Print the result for ( int i = 1; i <= n; i++) { cout << permutation[i] << " " ; } cout << endl; } } // Driver function int main() { int n = 4, x = 2; // Function call buildpermutation(n, x); int n2 = 5, x2 = 4; // Function call buildpermutation(n2, x2); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to build the permutation static void buildPermutation( int n, int x) { // Initialize the check[] array to // check whether the element to be // place at i th index is visited or not. boolean [] check = new boolean [n + 1 ]; // Initialize vector permutation to // store the final result permutation int [] permutation = new int [n + 1 ]; Arrays.fill(permutation, - 1 ); // Initialize a flag variable to check // if there is a possibility // to form a permutation int flag = 0 ; int i = 0 ; // As given in the question permutation[ 1 ] = x; permutation[n] = 1 ; // Mark 1 and x as visited as // they are placed check[ 1 ] = true ; check[x] = true ; // Traverse from 2 till n for (i = 2 ; i < n; i++) { // Now check for the number to be // placed at ith position to satisfy // the condition. Iterate from j = i // to all multiples of j to place // the lowest possible multiple for ( int j = i; j <= n; j += i) { // If the element itself is not // visited already the place it if (!check[j] && i == j) { permutation[i] = j; check[j] = true ; break ; } // Else check for a multiple // which is not visited and // divides n else if (!check[j] && (n % j) == 0 ) { permutation[i] = j; check[j] = true ; break ; } } // If the ith indexed element is // still -1 we are unable to find // an element to place so mark the // flag and break. if (permutation[i] == - 1 ) { flag++; break ; } } // Return -1 if not possible to // form a permutation if (flag > 0 ) { System.out.println(- 1 ); return ; } else { // Print the result for ( int k = 1 ; k <= n; k++) { System.out.print(permutation[k] + " " ); } System.out.println(); } } public static void main(String[] args) { int n = 4 , x = 2 ; // Function call buildPermutation(n, x); int n2 = 5 , x2 = 4 ; // Function call buildPermutation(n2, x2); } } // This code is contributed by lokesh. |
Python3
# Function to build the permutation def buildpermutation(n, x): # Initialize the check[] array to # check whether the element to be # place at i th index is visited or not. check = [ 0 for i in range (n + 1 )] # Initialize vector permutation to # store the final result permutation permutation = [ - 1 for i in range (n + 1 )] # Initialize a flag variable to check # if there is a possibility # to form a permutation flag = 0 i = 0 # As given in the question permutation[ 1 ] = x permutation[n] = 1 # Mark 1 and x as visited as # they are placed check[ 1 ] = True check[x] = True # Traverse from 2 till n for i in range ( 2 , n): # Now check for the number to be # placed at ith position to satisfy # the condition. Iterate from j = i # to all multiples of j to place # the lowest possible multiple for j in range (i, n + 1 , i): # If the element itself is not # visited already the place it if check[j] = = False and i = = j: permutation[i] = j check[j] = True break # Else check for a multiple # which is not visited and # divides n elif check[j] = = False and (n % j) = = 0 : permutation[i] = j check[j] = True break # If the ith indexed element is # still -1 we are unable to find # an element to place so mark the # flag and break. if permutation[i] = = - 1 : flag + = 1 break # Return -1 if not possible to # form a permutation if flag > 0 : print ( - 1 ) return else : # Print the result print (permutation[ 1 :]) # Driver function if __name__ = = '__main__' : n = 4 x = 2 # Function call buildpermutation(n, x) n2 = 5 x2 = 4 # Function call buildpermutation(n2, x2) |
Javascript
function buildPermutation(n, x) { // Initialize the check[] array to // check whether the element to be // place at i th index is visited or not. let check = Array(n + 1).fill( false ); // Initialize an array permutation to // store the final result permutation let permutation = Array(n + 1).fill(-1); // Initialize a flag variable to check // if there is a possibility // to form a permutation let flag = 0; let i = 0; // As given in the question permutation[1] = x; permutation[n] = 1; // Mark 1 and x as visited as // they are placed check[1] = true ; check[x] = true ; // Traverse from 2 till n for (i = 2; i < n; i++) { // Now check for the number to be // placed at ith position to satisfy // the condition. Iterate from j = i // to all multiples of j to place // the lowest possible multiple for (let j = i; j <= n; j += i) { // If the element itself is not // visited already the place it if (!check[j] && i === j) { permutation[i] = j; check[j] = true ; break ; } // Else check for a multiple // which is not visited and // divides n else if (!check[j] && (n % j) === 0) { permutation[i] = j; check[j] = true ; break ; } } // If the ith indexed element is // still -1 we are unable to find // an element to place so mark the // flag and break. if (permutation[i] === -1) { flag++; break ; } } // Return -1 if not possible to // form a permutation if (flag > 0) { console.log(-1); return ; } else { // Print the result console.log(permutation.slice(1)); } } // Driver function ( function main() { let n = 4, x = 2; // Function call buildPermutation(n, x); let n2 = 5, x2 = 4; // Function call buildPermutation(n2, x2); })(); // This code is contributed by hardikkushwaha |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to build the permutation static void buildpermutation( int n, int x) { // Initialize the check[] array to // check whether the element to be // place at i th index is visited or not. bool [] check= new bool [n + 1]; int i = 0; for ( i=0; i<n+1; i++) check[i]= false ; // Initialize vector permutation to // store the final result permutation int [] permutation= new int [n + 1]; for ( i=0; i<n+1; i++) permutation[i]=-1; // Initialize a flag variable to check // if there is a possibility // to form a permutation int flag = 0; // As given in the question permutation[1] = x; permutation[n] = 1; // Mark 1 and x as visited as // they are placed check[1] = true ; check[x] = true ; // Traverse from 2 till n for (i = 2; i < n; i++) { // Now check for the number to be // placed at ith position to satisfy // the condition. Iterate from j = i // to all multiples of j to place // the lowest possible multiple for ( int j = i; j <= n; j += i) { // If the element itself is not // visited already the place it if (check[j] == false && i == j) { permutation[i] = j; check[j] = true ; break ; } // Else check for a multiple // which is not visited and // divides n else if (check[j] == false && (n % j) == 0) { permutation[i] = j; check[j] = true ; break ; } } // If the ith indexed element is // still -1 we are unable to find // an element to place so mark the // flag and break. if (permutation[i] == -1) { flag++; break ; } } // Return -1 if not possible to // form a permutation if (flag > 0) { Console.WriteLine(-1); return ; } else { // Print the result for ( i = 1; i <= n; i++) { Console.Write(permutation[i]+ " " ); } Console.WriteLine(); } } // Driver function static void Main( string [] args) { int n = 4, x = 2; // Function call buildpermutation(n, x); int n2 = 5, x2 = 4; // Function call buildpermutation(n2, x2); } } |
2 4 3 1 -1
Time Complexity: O(nlogn), where n is the size of the array.
Auxiliary Space: O(n)