Find a permutation of 2N numbers such that the result of given expression is exactly 2K
Given two integers N and K, the task is to find a permutation of first 2*N natural numbers such that the following equation is satisfied.
Note: The value of K will always be less than or equal to N.
Examples:
Input : N = 1, K = 0 Output : 1 2 The result of the above expression will be: |1-2|-|1-2| =0 Input : N = 2, K = 1 Output : 2 1 3 4 The result of the above expression will be: (|2-1|+|3-4|)-(|2-1+3-4|) = 2
Approach:
Consider the sorted permutation:
1, 2, 3, 4, 5, 6....
The result of the expression will come out to be exactly 0. If we swap any 2 indices 2i-1 and 2i, the result will increase by exactly 2. So we need to make K such swaps.
Below is the implementation of the above approach:
C++
// C++ program to find the required permutation // of first 2*N natural numbers #include <bits/stdc++.h> using namespace std; // Function to find the required permutation // of first 2*N natural numbers void printPermutation( int n, int k) { // Iterate in blocks of 2 for ( int i = 1; i <= n; i++) { int x = 2 * i - 1; int y = 2 * i; // We need more increments, so print in reverse order if (i <= k) cout << y << " " << x << " " ; // We have enough increments, so print in same order else cout << x << " " << y << " " ; } } // Driver Code int main() { int n = 2, k = 1; printPermutation(n, k); return 0; } |
Java
// Java program to find the // required permutation // of first 2*N natural numbers class GFG { // Function to find the required permutation // of first 2*N natural numbers static void printPermutation( int n, int k) { // Iterate in blocks of 2 for ( int i = 1 ; i <= n; i++) { int x = 2 * i - 1 ; int y = 2 * i; // We need more increments, // so print in reverse order if (i <= k) System.out.print(y + " " + x + " " ); // We have enough increments, // so print in same order else System.out.print(x + " " + y + " " ); } } // Driver code public static void main(String []args) { int n = 2 , k = 1 ; printPermutation(n, k); } } // This code is contributed by Ita_c. |
Python3
# Python3 program to find the required # permutation of first 2*N natural numbers # Function to find the required permutation # of first 2*N natural numbers def printPermutation(n, k) : # Iterate in blocks of 2 for i in range ( 1 , n + 1 ) : x = 2 * i - 1 ; y = 2 * i; # We need more increments, # so print in reverse order if (i < = k) : print (y, x, end = " " ); # We have enough increments, # so print in same order else : print (x, y, end = " " ); # Driver Code if __name__ = = "__main__" : n = 2 ; k = 1 ; printPermutation(n, k); # This code is contributed by Ryuga |
C#
using System; // C# program to find the // required permutation // of first 2*N natural numbers class GFG { // Function to find the required permutation // of first 2*N natural numbers static void printPermutation( int n, int k) { // Iterate in blocks of 2 for ( int i = 1; i <= n; i++) { int x = 2 * i - 1; int y = 2 * i; // We need more increments, // so print in reverse order if (i <= k) Console.Write(y + " " + x + " " ); // We have enough increments, // so print in same order else Console.Write(x + " " + y + " " ); } } // Driver code public static void Main() { int n = 2, k = 1; printPermutation(n, k); } } // This code is contributed by // shashank_sharma |
PHP
<?php // PHP program to find the required // permutation of first 2*N natural numbers // Function to find the required permutation // of first 2*N natural numbers function printPermutation( $n , $k ) { // Iterate in blocks of 2 for ( $i = 1; $i <= $n ; $i ++) { $x = 2 * $i - 1; $y = 2 * $i ; // We need more increments, so print // in reverse order if ( $i <= $k ) echo $y . " " . $x . " " ; // We have enough increments, // so print in same order else echo $x . " " . $y . " " ; } } // Driver Code $n = 2; $k = 1; printPermutation( $n , $k ); // This code is contributed by chandan_jnu ?> |
Javascript
<script> // javascript program to find the // required permutation // of first 2*N natural numbers // Function to find the required permutation // of first 2*N natural numbers function printPermutation( n, k) { // Iterate in blocks of 2 for ( var i = 1; i <= n; i++) { var x = 2 * i - 1; var y = 2 * i; // We need more increments, // so print in reverse order if (i <= k) document.write(y + " " + x + " " ); // We have enough increments, // so print in same order else document.write(x + " " + y + " " ); } } // Driver code var n = 2, k = 1; printPermutation(n, k); // This code is contributed by bunnyram19. </script> |
Output:
2 1 3 4
Time Complexity: O(N), since there runs a loop from 1 to n.
Auxiliary Space: O(1), since no extra space has been taken.