Given an array arr[] consisting of 2* N elements in the form of { a1, a2, …, aN, b1, b2, …, bN }, the task is to shuffle the array to {a1, b1, a2, b2, …, an, b1} without using extra space.
Examples :
Input: arr[] = { 1, 3, 5, 2, 4, 6 }
Output: 1 2 3 4 5 6
Explanation:
The output contains the elements in the form of { a1, b1, a2, b2, a3, b3 }.Input: arr[] = {1, 2, 3, -1, -2, -3, }
Output: 1 -1 2 -2 3 -3
Divide and Conquer-based Approach: If the size of an array is a power of 2, then follow the article Shuffle 2n integers in format {a1, b1, a2, b2, a3, b3, ……, an, bn} using divide and conquer technique.
Time Complexity: O(N * log(N))
Auxiliary Space: O(1)
Alternate Approach: The above approach will work for all possible values of N by recursively dividing the array such that the length of both halves is even. Follow the steps below to solve the problem:
- Define a recursive function, say shuffle(start, end).
- If array length is divisible by 4, then calculate mid-point of the array, say mid = start + (end – start + 1) / 2.
- Otherwise, mid = start + (end – start + 1) / 2 – 1.
- Calculate mid-points of both subarrays, say mid1 = start + (mid – start)/2, and mid2 = mid + (end – mid + 1) / 2.
- Reverse the subarrays in the ranges [mid1, mid2], [mid1, mid-1], and [mid, mid2 – 1].
- Make recursive calls for subarrays [start, mid – 1] and [mid, end], i.e. shuffle(start, mid – 1) and shuffle(mid, end) respectively.
- Finally, print the array.
Illustration:
Consider an array arr[] = {a1, a2, a3, b1, b2, b3}:
- Split the array into two halves, both of even length, i.e. a1, a2 : a3, b1, b2, b3.
- Reverse the mid of first half to mid of 2nd half, i.e. a1, b1 : a3, a2, b2, b3.
- Now, reverse the mid of first half to mid of subarray [0, 5], a1, b1 : a3, a2, b2, b3.
- Now reverse mid of subarray [0, 5] to mid of 2nd half, a1, b1 : a2, a3, b2, b3.
- Recursively call for arrays {a1, b1}, and {a2, a3, b2, b3}.
- Now the array {a2, a3, b2, b3} modifies to {a2, b2, a3, b3} after applying the above operations.
- Now the arr[] modifies to {a1, b1, a2, b2, a3, b3}.
Below is the implementation of the above approach:
C
// C program for the above approach #include <stdio.h> // Function to reverse the array from the // position 'start' to position 'end' void reverse( int arr[], int start, int end) { // Stores mid of start and end int mid = (end - start + 1) / 2; // Traverse the array in // the range [start, end] for ( int i = 0; i < mid; i++) { // Stores arr[start + i] int temp = arr[start + i]; // Update arr[start + i] arr[start + i] = arr[end - i]; // Update arr[end - i] arr[end - i] = temp; } return ; } // Utility function to shuffle the given array // in the of form {a1, b1, a2, b2, ....an, bn} void shuffleArrayUtil( int arr[], int start, int end) { int i; // Stores the length of the array int l = end - start + 1; // If length of the array is 2 if (l == 2) return ; // Stores mid of the { start, end } int mid = start + l / 2; // Divide array into two // halves of even length if (l % 4) { // Update mid mid -= 1; } // Calculate the mid-points of // both halves of the array int mid1 = start + (mid - start) / 2; int mid2 = mid + (end + 1 - mid) / 2; // Reverse the subarray made // from mid1 to mid2 reverse(arr, mid1, mid2 - 1); // Reverse the subarray made // from mid1 to mid reverse(arr, mid1, mid - 1); // Reverse the subarray made // from mid to mid2 reverse(arr, mid, mid2 - 1); // Recursively calls for both // the halves of the array shuffleArrayUtil(arr, start, mid - 1); shuffleArrayUtil(arr, mid, end); } // Function to shuffle the given array in // the form of {a1, b1, a2, b2, ....an, bn} void shuffleArray( int arr[], int N, int start, int end) { // Function Call shuffleArrayUtil(arr, start, end); // Print the modified array for ( int i = 0; i < N; i++) printf ( "%d " , arr[i]); } // Driver Code int main() { // Given array int arr[] = { 1, 3, 5, 2, 4, 6 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Shuffles the given array to the // required permutation shuffleArray(arr, N, 0, N - 1); return 0; } |
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to reverse the array from the // position 'start' to position 'end' void reverse( int arr[], int start, int end) { // Stores mid of start and end int mid = (end - start + 1) / 2; // Traverse the array in // the range [start, end] for ( int i = 0; i < mid; i++) { // Stores arr[start + i] int temp = arr[start + i]; // Update arr[start + i] arr[start + i] = arr[end - i]; // Update arr[end - i] arr[end - i] = temp; } return ; } // Utility function to shuffle the given array // in the of form {a1, b1, a2, b2, ....an, bn} void shuffleArrayUtil( int arr[], int start, int end) { int i; // Stores the length of the array int l = end - start + 1; // If length of the array is 2 if (l == 2) return ; // Stores mid of the { start, end } int mid = start + l / 2; // Divide array into two // halves of even length if (l % 4) { // Update mid mid -= 1; } // Calculate the mid-points of // both halves of the array int mid1 = start + (mid - start) / 2; int mid2 = mid + (end + 1 - mid) / 2; // Reverse the subarray made // from mid1 to mid2 reverse(arr, mid1, mid2 - 1); // Reverse the subarray made // from mid1 to mid reverse(arr, mid1, mid - 1); // Reverse the subarray made // from mid to mid2 reverse(arr, mid, mid2 - 1); // Recursively calls for both // the halves of the array shuffleArrayUtil(arr, start, mid - 1); shuffleArrayUtil(arr, mid, end); } // Function to shuffle the given array in // the form of {a1, b1, a2, b2, ....an, bn} void shuffleArray( int arr[], int N, int start, int end) { // Function Call shuffleArrayUtil(arr, start, end); // Print the modified array for ( int i = 0; i < N; i++) cout << arr[i] << " " ; } // Driver Code int main() { // Given array int arr[] = { 1, 3, 5, 2, 4, 6 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // Shuffles the given array to the // required permutation shuffleArray(arr, N, 0, N - 1); return 0; } // This code is contributed by jainlovely450. |
Java
// Java program for the above approach class GFG{ // Function to reverse the array from the // position 'start' to position 'end' static void reverse( int arr[], int start, int end) { // Stores mid of start and end int mid = (end - start + 1 ) / 2 ; // Traverse the array in // the range [start, end] for ( int i = 0 ; i < mid; i++) { // Stores arr[start + i] int temp = arr[start + i]; // Update arr[start + i] arr[start + i] = arr[end - i]; // Update arr[end - i] arr[end - i] = temp; } return ; } // Utility function to shuffle the given array // in the of form {a1, b1, a2, b2, ....an, bn} static void shuffleArrayUtil( int arr[], int start, int end) { int i; // Stores the length of the array int l = end - start + 1 ; // If length of the array is 2 if (l == 2 ) return ; // Stores mid of the { start, end } int mid = start + l / 2 ; // Divide array into two // halves of even length if (l % 4 > 0 ) { // Update mid mid -= 1 ; } // Calculate the mid-points of // both halves of the array int mid1 = start + (mid - start) / 2 ; int mid2 = mid + (end + 1 - mid) / 2 ; // Reverse the subarray made // from mid1 to mid2 reverse(arr, mid1, mid2 - 1 ); // Reverse the subarray made // from mid1 to mid reverse(arr, mid1, mid - 1 ); // Reverse the subarray made // from mid to mid2 reverse(arr, mid, mid2 - 1 ); // Recursively calls for both // the halves of the array shuffleArrayUtil(arr, start, mid - 1 ); shuffleArrayUtil(arr, mid, end); } // Function to shuffle the given array in // the form of {a1, b1, a2, b2, ....an, bn} static void shuffleArray( int arr[], int N, int start, int end) { // Function Call shuffleArrayUtil(arr, start, end); // Print the modified array for ( int i = 0 ; i < N; i++) System.out.printf( "%d " , arr[i]); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 1 , 3 , 5 , 2 , 4 , 6 }; // Size of the array int N = arr.length; // Shuffles the given array to the // required permutation shuffleArray(arr, N, 0 , N - 1 ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function to reverse the array from the # position 'start' to position 'end' def reverse(arr, start, end): # Stores mid of start and end mid = (end - start + 1 ) / / 2 # Traverse the array in # the range [start, end] for i in range (mid): # Stores arr[start + i] temp = arr[start + i] # Update arr[start + i] arr[start + i] = arr[end - i] # Update arr[end - i] arr[end - i] = temp return arr # Utility function to shuffle the given array # in the of form {a1, b1, a2, b2, ....an, bn} def shuffleArrayUtil(arr, start, end): i = 0 # Stores the length of the array l = end - start + 1 # If length of the array is 2 if (l = = 2 ): return # Stores mid of the { start, end } mid = start + l / / 2 # Divide array into two # halves of even length if (l % 4 ): # Update mid mid - = 1 # Calculate the mid-points of # both halves of the array mid1 = start + (mid - start) / / 2 mid2 = mid + (end + 1 - mid) / / 2 # Reverse the subarray made # from mid1 to mid2 arr = reverse(arr, mid1, mid2 - 1 ) # Reverse the subarray made # from mid1 to mid arr = reverse(arr, mid1, mid - 1 ) # Reverse the subarray made # from mid to mid2 arr = reverse(arr, mid, mid2 - 1 ) # Recursively calls for both # the halves of the array shuffleArrayUtil(arr, start, mid - 1 ) shuffleArrayUtil(arr, mid, end) # Function to shuffle the given array in # the form of {a1, b1, a2, b2, ....an, bn} def shuffleArray(arr, N, start, end): # Function Call shuffleArrayUtil(arr, start, end) # Print the modified array for i in arr: print (i, end = " " ) # Driver Code if __name__ = = '__main__' : # Given array arr = [ 1 , 3 , 5 , 2 , 4 , 6 ] # Size of the array N = len (arr) # Shuffles the given array to the # required permutation shuffleArray(arr, N, 0 , N - 1 ) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; public class GFG{ // Function to reverse the array from the // position 'start' to position 'end' static void reverse( int [] arr, int start, int end) { // Stores mid of start and end int mid = (end - start + 1) / 2; // Traverse the array in // the range [start, end] for ( int i = 0; i < mid; i++) { // Stores arr[start + i] int temp = arr[start + i]; // Update arr[start + i] arr[start + i] = arr[end - i]; // Update arr[end - i] arr[end - i] = temp; } return ; } // Utility function to shuffle the given array // in the of form {a1, b1, a2, b2, ....an, bn} static void shuffleArrayUtil( int [] arr, int start, int end) { // Stores the length of the array int l = end - start + 1; // If length of the array is 2 if (l == 2) return ; // Stores mid of the { start, end } int mid = start + l / 2; // Divide array into two // halves of even length if (l % 4 > 0) { // Update mid mid -= 1; } // Calculate the mid-points of // both halves of the array int mid1 = start + (mid - start) / 2; int mid2 = mid + (end + 1 - mid) / 2; // Reverse the subarray made // from mid1 to mid2 reverse(arr, mid1, mid2 - 1); // Reverse the subarray made // from mid1 to mid reverse(arr, mid1, mid - 1); // Reverse the subarray made // from mid to mid2 reverse(arr, mid, mid2 - 1); // Recursively calls for both // the halves of the array shuffleArrayUtil(arr, start, mid - 1); shuffleArrayUtil(arr, mid, end); } // Function to shuffle the given array in // the form of {a1, b1, a2, b2, ....an, bn} static void shuffleArray( int [] arr, int N, int start, int end) { // Function Call shuffleArrayUtil(arr, start, end); // Print the modified array for ( int i = 0; i < N; i++) Console.Write(arr[i] + " " ); } // Driver Code static public void Main () { // Given array int [] arr = { 1, 3, 5, 2, 4, 6 }; // Size of the array int N = arr.Length; // Shuffles the given array to the // required permutation shuffleArray(arr, N, 0, N - 1); } } // This code is contributed by Dharanendra L V |
Javascript
<script> // Javascript program of the above approach // Function to reverse the array from the // position 'start' to position 'end' function reverse(arr, start, end) { // Stores mid of start and end let mid = (end - start + 1) / 2; // Traverse the array in // the range [start, end] for (let i = 0; i < mid; i++) { // Stores arr[start + i] let temp = arr[start + i]; // Update arr[start + i] arr[start + i] = arr[end - i]; // Update arr[end - i] arr[end - i] = temp; } return ; } // Utility function to shuffle the given array // in the of form {a1, b1, a2, b2, ....an, bn} function shuffleArrayUtil(arr, start, end) { let i; // Stores the length of the array let l = end - start + 1; // If length of the array is 2 if (l == 2) return ; // Stores mid of the { start, end } let mid = start + l / 2; // Divide array into two // halves of even length if (l % 4 > 0) { // Update mid mid -= 1; } // Calculate the mid-points of // both halves of the array let mid1 = start + (mid - start) / 2; let mid2 = mid + (end + 1 - mid) / 2; // Reverse the subarray made // from mid1 to mid2 reverse(arr, mid1, mid2 - 1); // Reverse the subarray made // from mid1 to mid reverse(arr, mid1, mid - 1); // Reverse the subarray made // from mid to mid2 reverse(arr, mid, mid2 - 1); // Recursively calls for both // the halves of the array shuffleArrayUtil(arr, start, mid - 1); shuffleArrayUtil(arr, mid, end); } // Function to shuffle the given array in // the form of {a1, b1, a2, b2, ....an, bn} function shuffleArray(arr, N, start, end) { // Function Call shuffleArrayUtil(arr, start, end); // Print the modified array for (let i = 0; i < N; i++) document.write(arr[i] + " " ); } // Driver Code // Given array let arr = [ 1, 3, 5, 2, 4, 6 ]; // Size of the array let N = arr.length; // Shuffles the given array to the // required permutation shuffleArray(arr, N, 0, N - 1); </script> |
1 2 3 4 5 6
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!