DEV Community

Cover image for #1470 Crazy mathematics. Shuffle the Array in place O(1);
Rajesh Royal
Rajesh Royal

Posted on

#1470 Crazy mathematics. Shuffle the Array in place O(1);

Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].

Return the array in the form [x1,y1,x2,y2,...,xn,yn].
Example -

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 
then the answer is [2,3,5,4,1,7].
Enter fullscreen mode Exit fullscreen mode

In this technique we try to store two numbers at one Index by multiplying the number with 10000;
As we know our Constraints number can be up to 1000 so we are multiplying it with 10000, so that if the numbers are of 4 digits we can store all of them.
This multiplying number can be increased as per our input number size increases.

⚠ I'm using pointers for easy explanation but we can do it without them.

Explanation

Step 1.

In first loop we store two numbers at one index.

// let's say Our input is [1,2,3,4,5,6]
Enter fullscreen mode Exit fullscreen mode

We will run our first loop from 0 to n / 2 - 1 and n / 2 to n - 1; So basically first pointer will run for [1,2,3] and second pointer will run for [4,5,6].
And we will keep multiplying the rightPointer to 10000 and add our leftPointer to result and store it at leftPointer position.

let leftPointer = 0;
let rightPointer = nums.length / 2;

while(leftPointer < nums.length / 2 && rightPointer < nums.length){
   nums[leftPointer] = nums[rightPointer]+(nums[leftPointer] * 10000);

   leftPointer++;
   rightPointer++;
}
Enter fullscreen mode Exit fullscreen mode

Now my result array becomes - [10004, 20005, 30006, 4, 5, 6];

Step 2.

Now In our second loop we divide and mod the converted number and place the result at respective place.
This time we will start our indexes in reverse order.

  • LeftPointer will start from nums.length / 2 - 1 and go to 0; We decrease it by 1 each time.
  • RightPointer will start from nums.length - 1. We will decrease it by 2 each time because we store 2 items at end.

So in first loop our rightPointer will point to [6] and our leftPointer will point to 3006.

And when we divide and mode [30006] by 10000 we get 3 and 6 
now store these 3 and 6 at the end of the nums[].
And we keep doing it until we reaches 0th position of array.
Enter fullscreen mode Exit fullscreen mode

See the below loop, we initialized left and right pointers respectively and looping over the big numbers which we created in earlier loop. Now we get the resultant two numbers and store them at the rightPointer.

leftPointer = nums.length / 2 - 1
rightPointer = nums.length - 1;
while(leftPointer >= 0){
  nums[rightPointer] = nums[leftPointer] % 10000;
  nums[rightPointer - 1] = ~(~(nums[leftPointer] / 10000));

  leftPointer--;
  rightPointer -= 2;
}
Enter fullscreen mode Exit fullscreen mode

Source code.

/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number[]}
 */

var shuffle = function(nums, n){
    let leftPointer = 0;
    let rightPointer = nums.length / 2;

    while(leftPointer < nums.length / 2 && rightPointer < nums.length){
        nums[leftPointer] = nums[rightPointer]+(nums[leftPointer] * 10000);

        leftPointer++;
        rightPointer++;
    }
    leftPointer = nums.length / 2 - 1
    rightPointer = nums.length - 1;
     while(leftPointer >= 0){
        nums[rightPointer] = nums[leftPointer] % 10000;
        nums[rightPointer - 1] = ~(~(nums[leftPointer] / 10000));

        leftPointer--;
        rightPointer -= 2;
     }
    return nums;
}
Enter fullscreen mode Exit fullscreen mode

Shuffle the array leetcode
👋

Discussion (4)

Collapse
damian_cyrus profile image
Damian Cyrus

Little off topic suggestion:

  • split the code into multiple functions
  • put some values into variables, to make it easier to understand
  • write an explanation for each function in jsdoc
  • add a unit test to test each function separated, to be very sure js is doing what it is expected
  • set up a gist or even a repo to test the code

On topic: thank you for the deep dive details 👍 it's nice to see that we still need it 😁

Collapse
rajeshroyal profile image
Rajesh Royal Author

Off topic - I don't like a post, I ignore it.

On topic - I like the humour 😄

Collapse
ninjainpajama profile image
ninja in pajama

dumbfound

Collapse
normalgui profile image
Normal GU-I

lol🤣 where did you get that.