Shuffle Array [Bit manipulation]

85.Shuffle the Array

Array

Bit Manipulation

Problem Statement:

Given an array nums consisting of 2n elements in the format [x1, x2, ..., xn, y1, y2, ..., yn], shuffle the array to return [x1, y1, x2, y2, ..., xn, yn].

Algorithm:

1. Use bit manipulation to pack two integers into a single integer at each index for the first half of the array:
• Shift the second number (y) 10 bits to the left.
• Use bitwise OR to combine it with the first number (x).
2. Iterate from the end of the first half backward and unpack the numbers:
• Extract the second number using a right shift.
• Extract the first number using a bitwise AND with a mask of 10 ones (0000000000 1111111111).
• Place the numbers at their appropriate positions in the shuffled format.

Complexity:

Time: O(n) | Space: O(1)

Java Implementation:

public int[] shuffle(int[] nums, int n) {
    // Store each y(i) with its respective x(i) in the first half of the array
    for (int i = n; i < 2 * n; ++i) {
        int secondNum = nums[i] << 10;  // Shift y(i) by 10 bits
        nums[i - n] |= secondNum;       // Combine x(i) and y(i) using bitwise OR
    }

    int allOnes = (1 << 10) - 1;  // Mask to extract the first 10 bits (decimal 1023)

    // Place numbers in their correct positions
    for (int i = n - 1; i >= 0; --i) {
        int secondNum = nums[i] >> 10; // Extract y(i) by right-shifting 10 bits
        int firstNum = nums[i] & allOnes; // Extract x(i) using the mask
        nums[2 * i + 1] = secondNum;
        nums[2 * i] = firstNum;
    }

    return nums;
}

Python Implementation:

def shuffle(nums, n):
    # Store each y(i) with its respective x(i) in the first half
    for i in range(n, 2 * n):
        second_num = nums[i] << 10  # Shift y(i) by 10 bits
        nums[i - n] |= second_num   # Combine x(i) and y(i) using bitwise OR

    all_ones = (1 << 10) - 1  # Mask to extract the first 10 bits

    # Place numbers in their correct positions
    for i in range(n - 1, -1, -1):
        second_num = nums[i] >> 10  # Extract y(i)
        first_num = nums[i] & all_ones  # Extract x(i)
        nums[2 * i + 1] = second_num
        nums[2 * i] = first_num

    return nums

C++ Implementation:

#include 
using namespace std;

vector shuffle(vector& nums, int n) {
    // Store each y(i) with its respective x(i) in the first half
    for (int i = n; i < 2 * n; ++i) {
        int secondNum = nums[i] << 10;  // Shift y(i) by 10 bits
        nums[i - n] |= secondNum;       // Combine x(i) and y(i) using bitwise OR
    }

    int allOnes = (1 << 10) - 1;  // Mask to extract the first 10 bits

    // Place numbers in their correct positions
    for (int i = n - 1; i >= 0; --i) {
        int secondNum = nums[i] >> 10;  // Extract y(i)
        int firstNum = nums[i] & allOnes;  // Extract x(i)
        nums[2 * i + 1] = secondNum;
        nums[2 * i] = firstNum;
    }

    return nums;
}