Find permutation of first N natural numbers that satisfies the given condition
Given two integer N and K, the task is to find the permutation P of first N natural numbers such that there are exactly K elements which satisfies the condition GCD(P[i], i) > 1 for all 1 ? i ? N.
Examples:
Input: N = 3, K = 1
Output: 2 1 3
GCD(P[1], 1) = GCD(2, 1) = 1
GCD(P[2], 2) = GCD(1, 2) = 1
GCD(P[3], 3) = GCD(3, 3) = 3
There is exactly 1 element such that GCD(P[i], i) > 1
Input: N = 5, K = 2
Output: 3 1 2 4 5
Approach: Keep the last K elements in their place. The rest of the elements are moved such that ith element is placed in (i + 1)th position and (N – K)th element is kept in position 1 because gcd(x, x + 1) = 1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 void Permutation( int n, int k) { int p[n + 1]; // First place all the numbers // in their respective places for ( int i = 1; i <= n; i++) p[i] = i; // Modify for first n-k integers for ( int i = 1; i < n - k; i++) p[i + 1] = i; // In first index place n-k p[1] = n - k; // Print the permutation for ( int i = 1; i <= n; i++) cout << p[i] << " " ; } // Driver code int main() { int n = 5, k = 2; Permutation(n, k); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 static void Permutation( int n, int k) { int [] p = new int [n + 1 ]; // First place all the numbers // in their respective places for ( int i = 1 ; i <= n; i++) p[i] = i; // Modify for first n-k integers for ( int i = 1 ; i < n - k; i++) p[i + 1 ] = i; // In first index place n-k p[ 1 ] = n - k; // Print the permutation for ( int i = 1 ; i <= n; i++) System.out.print(p[i] + " " ); } // Driver code public static void main(String[] args) { int n = 5 , k = 2 ; Permutation(n, k); } } // This code is contributed by Naman_Garg |
Python3
# Python 3 implementation of the approach # Function to find permutation(p) # of first N natural numbers such that # there are exactly K elements of # permutation such that GCD(p[i], i)>1 def Permutation(n, k): p = [ 0 for i in range (n + 1 )] # First place all the numbers # in their respective places for i in range ( 1 , n + 1 ): p[i] = i # Modify for first n-k integers for i in range ( 1 , n - k): p[i + 1 ] = i # In first index place n-k p[ 1 ] = n - k # Print the permutation for i in range ( 1 , n + 1 ): print (p[i], end = " " ) # Driver code if __name__ = = '__main__' : n = 5 k = 2 Permutation(n, k) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 static void Permutation( int n, int k) { int [] p = new int [n + 1]; // First place all the numbers // in their respective places for ( int i = 1; i <= n; i++) p[i] = i; // Modify for first n-k integers for ( int i = 1; i < n - k; i++) p[i + 1] = i; // In first index place n-k p[1] = n - k; // Print the permutation for ( int i = 1; i <= n; i++) Console.Write(p[i] + " " ); } // Driver code static public void Main () { int n = 5, k = 2; Permutation(n, k); } } // This code is contributed by ajit. |
PHP
<?php // PHP implementation of the approach // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 function Permutation( $n , $k ) { $p = array (); // First place all the numbers // in their respective places for ( $i = 1; $i <= $n ; $i ++) $p [ $i ] = $i ; // Modify for first n-k integers for ( $i = 1; $i < $n - $k ; $i ++) $p [ $i + 1] = $i ; // In first index place n-k $p [1] = $n - $k ; // Print the permutation for ( $i = 1; $i <= $n ; $i ++) echo $p [ $i ], " " ; } // Driver code $n = 5; $k = 2; Permutation( $n , $k ); // This code is contributed by AnkitRai01 ?> |
Javascript
<script> //Javascript implementation of the approach // Function to find permutation(p) of first N // natural numbers such that there are exactly K // elements of permutation such that GCD(p[i], i)>1 function Permutation(n, k) { let p = new Array(n + 1); // First place all the numbers // in their respective places for (let i = 1; i <= n; i++) p[i] = i; // Modify for first n-k integers for (let i = 1; i < n - k; i++) p[i + 1] = i; // In first index place n-k p[1] = n - k; // Print the permutation for (let i = 1; i <= n; i++) document.write(p[i] + " " ); } // Driver code let n = 5, k = 2; Permutation(n, k); // This code is contributed by Mayank Tyagi </script> |
Output:
3 1 2 4 5
Time Complexity: O(n)
Auxiliary Space: O(n)