Shuffle integers-gfg

25-11-2023, it's almost 11:50 near midnight, this problem that I took today as a potd for GFG, had the tricky and challenging( if not previously addressed ) concept of combining 2 numbers without loss of data... yah that's what I call this thing.

Basically the thing is that we gotta replace some elements of the array, the catch being that we cannot take any extra space, that sounds easy( yeah it's just some elems here and there that's it, BUT it's tricky...a bit ).

Now, the question is what is tricky in this? I have n/2 elems and then other n/2 elems and I also know the positions where to keep them, the 1st n/2 elems in the even positions, and the 2nd n/2 elems in the odd ones, but again, if you visualize yourself going through the array towards the end, for the 0 index you kept the 0th elem there, for 1th index you kept the n/2 th elem there, now where to keep the 1th elem?? 

Cause that's gonna go at index 2 and then what to do with the elem at that index? and then go on and go on until you are STUCK. 

If you are smart enough like me ;), then you are gonna understand that you are missing something, yeah, you can keep on going and keep placing the elems at their place and then replace the elems that are replaced like a recursive process. But eventually you don't have anyy solid plan on whether all the elems are gonna get covered in this process.

And to make sure that all the elems are placed in the correct position, we'll have to maintain some record, and that's gonna require O(n) space, hell... then what was the use of all this idea? So it's a bad idea.

The correct way out here is that "We are gonna combine 2 elems without loss of data". Yeah just that.

for ex. take 2 and 3, (now just know that we are gonna use a big_elem here that can be anything greater than the elems in the process). That big_elem let's take 5. 

So, I say 2+3*5, this is the combination of 2 and 3, if you look into this, then 17%5 is gonna give you original elem, that is 2. and 17//5 is gonna give you the elem that was added to 2, that is 3. This is the whole core of this problem, if you got this, then you are great, if not, then keep trying to get this, you'll get there.

The code should be sufficiently easy to understand now, just focus on the visualization of the problem in your mind and remember that the original elem will be (elem%big_elem).

Problem Statement:-

Given an array arr of n elements in the following format {a1, a2, a3, a4, ... , an/2, b1, b2, b3, b4, ... , bn/2}, the task is shuffle the array to {a1, b1, a2, b2, a3, b3, ... , an/2, bn/2} without using extra space.
Note that n is even.

Example 1:

Input: 
n = 4, arr = {1, 2, 9, 15}
Output:  
1 9 2 15
Explanation: 
a1=1, a2=2, b1=9, b2=15. So the final array will be: a1, b1, a2, b2 = {1,9,2,15}.

Example 2:

Input: 
n = 6 arr = {1, 2, 3, 4, 5, 6} 
Output: 
1 4 2 5 3 6

Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function shuffleArray() that takes array arr, and an integer n as parameters and modifies the given array according to the above-given pattern.

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).

Constraints:
1 ≤ n ≤ 105
1 ≤ arri ≤ 103

Code:-

class Solution:

    def shuffleArray(self, arr, n):

        # Your code goes here

        itr2=n//2

        itr1=0

        mx=max(arr)+1

        for i in range(n):

            if(i%2==0):

                # arr[i]=new_elem*mx+original_elem

                arr[i]=(arr[itr1]%mx)*mx+(arr[i]%mx)

                itr1+=1

            else:

                arr[i]=(arr[itr2]%mx)*mx+(arr[i]%mx)

                itr2+=1

        for i in range(n):

            arr[i]//=mx

        # print(arr)