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 numbersvoid 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 Codeint main(){ int n = 2, k = 1; printPermutation(n, k); return 0;} |
Java
// Java program to find the // required permutation// of first 2*N natural numbersclass 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 numbersfunction 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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!