Given an integer N, the task is to generate a permutation from 1 to N such that the bitwise XOR of differences between adjacent elements is 0 i.e., | A[1]− A[2] | ^ | A[2]− A[3] | ^ . . . ^ | A[N −1] − A[N] | = 0, where |X – Y| represents absolute difference between X and Y.
Examples:
Input: N = 4
Output: 2 3 1 4
Explanation: |2 -3| ^ |3 -1| ^ |1-4| = 1 ^ 2 ^ 3 = 0Input: N = 3
Output: 1 2 3
Approach: This problem can be solved based on the following observation:
- The XOR of even number of same elements is 0. So if odd number of elements are there (which implies even number of adjacent differences) then arrange them in a way such that the difference between any two adjacent elements is same.
- Else if N is even (which implies odd number of adjacent differences) then arrange the first four in such a way that the XOR of first three differences is 0. Then the remaining elements in the above mentioned away.
Follow the steps mentioned below to implement the above observation:
- If N is odd, arrange all the N elements in a sorted manner because the difference between any two adjacent elements will be 1 and the number of adjacent differences are even.
- If N is even:
- Keep 2, 3, 1, 4 as the first four elements because the 3 differences have XOR 0.
- Now start from 5 and print the remaining elements in sorted order, which will give the difference as 1 for all the remaining even number of differences.
Below is the implementation of the above approach.
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to print shuffle arrayvector<int> shuffleArray(int n){ vector<int> res; // Base case if (n < 3) cout << -1 << endl; // When n is odd print array in // increasing order else if (n % 2 != 0) { for (int i = 1; i <= n; i++) res.push_back(i); } // When n is even print first 2 3 1 4 // rest element in increasing order else { res = { 2, 3, 1, 4 }; for (int i = 5; i <= n; i++) res.push_back(i); } return res;}// Driver codeint main(){ int N = 4; vector<int> ans = shuffleArray(N); for (int x : ans) cout << x << " "; return 0;} |
Java
// Java implementation of above approachimport java.util.*;public class GFG { // Function to print shuffle array static ArrayList<Integer> shuffleArray(int n) { ArrayList<Integer> res = new ArrayList<Integer>(); // Base case if (n < 3) System.out.println(-1); // When n is odd print array in // increasing order else if (n % 2 != 0) { for (int i = 1; i <= n; i++) res.add(i); } // When n is even print first 2 3 1 4 // rest element in increasing order else { res.clear(); res.add(2); res.add(3); res.add(1); res.add(4); for (int i = 5; i <= n; i++) res.add(i); } return res; } // Driver code public static void main(String args[]) { int N = 4; ArrayList<Integer> ans = shuffleArray(N); for (int i = 0; i < ans.size(); i++) System.out.print(ans.get(i) + " "); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python3 implementation of above approach# Function to print shuffle arraydef shuffleArray(n): res = [] # Base case if (n < 3): print(-1) # When n is odd print array in # increasing order elif (n % 2 != 0): for i in range(1, n): res.append(i) # When n is even print first 2 3 1 4 # rest element in increasing order else: res = [2, 3, 1, 4] for i in range(5, n): res.append(i) return res# Driver codeif __name__ == '__main__': n = 4 res = shuffleArray(n) for i in res: print(i, end=' ') # This code is contributed by richasalan57. |
C#
// C# implementation of above approachusing System;using System.Collections;class GFG{// Function to print shuffle arraystatic ArrayList shuffleArray(int n){ ArrayList res = new ArrayList(); // Base case if (n < 3) Console.WriteLine(-1); // When n is odd print array in // increasing order else if (n % 2 != 0) { for (int i = 1; i <= n; i++) res.Add(i); } // When n is even print first 2 3 1 4 // rest element in increasing order else { res.Clear(); res.Add(2); res.Add(3); res.Add(1); res.Add(4); for (int i = 5; i <= n; i++) res.Add(i); } return res;}// Driver codepublic static void Main(){ int N = 4; ArrayList ans = shuffleArray(N); foreach (int x in ans) Console.Write(x + " ");}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript implementation of above approach// Function to print shuffle arrayfunction shuffleArray(n){ let res = []; // Base case if (n < 3) document.write(-1,"</br>"); // When n is odd print array in // increasing order else if (n % 2 != 0) { for (let i = 1; i <= n; i++) res.push(i); } // When n is even print first 2 3 1 4 // rest element in increasing order else { res = [ 2, 3, 1, 4 ]; for (let i = 5; i <= n; i++) res.push(i); } return res;}// Driver codelet N = 4;let ans = shuffleArray(N);for(let x of ans) document.write(x," ");// This code is contributed by shinjanpatra</script> |
Output
2 3 1 4
Time Complexity: O(N)
Auxiliary space: O(N) because it is using extra space for vector res
