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 Codeint 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 Codeint 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 approachclass 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 Codepublic 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 Codeif __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 approachusing 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 Codestatic 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> |
Output:
1 2 3 4 5 6
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
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!
