Hi there! So September Long challenge is on. And here is another problem from CodeChef. Named as Shuffling Parities. Please check here for full problem statement.

In this, I will explain my easy approach to the problem which has time complexity of O(n). At the end of this article , you will be able to write your own solution to the problem 😄.

Constraints :

  • An array A of N length is given with all positive integers.
  • The shuffle is required such that sum of (Ai + i)%2 is maximum, where Ai refers to each integer at index i and i refers to the index value starting from 1 to N.

Analysis :

  • We can directly deduce that x % 2 always yields either 0 or 1 [0,1]. And we know we need to have 1 as result for all possible integers in array to sum up to the maximum.
  • Now we know x%2 results in 1 when x is a Odd number. Here x is the sum of Ai and i.
  • Hence to get odd number from them, we can try two combinations : 1. Take odd Ai and even i. Example : For A=[1,2], Ai=1 and i=2, so (1+2)=3 2. Take even Ai and odd i. Example : For A=[1,2], Ai=2 and i=1, so (2+1)=3 So now we can reform A=[2,1] for maximum sum of 2.

Approach :

Now instead of shuffling, we can visualize to reform the array with all even Ai at odd indexes i and all odd Ai at even indexes i. In this way, we will be able to find the maximum sum.

  • To do the above, first we need to count the total number of even and odd indexes we have in array. This can be calculated as - If N is length of array then, even_i=N/2 and odd_i=N-even_i
  • Secondly, we need to find how many even and odd integers are there in the Array. We can traverse the array and check for each integer. ( if Ai%2==0, then Ai is even else odd ) Let's keep the count at arr_odd and arr_even.
  • Then , we check if we can accommodate all the arr_odd in the even_i and all the arr_even in odd_i. If any extra are remaining, we can keep it in separate variable( initialized with 0 ). 1. extra1= arr_odd-even_i if arr_odd > even_i 2. extra2= arr_even-odd_i if arr_even >odd_i
  • Now last step, we know how many we can accommodate by subtracting extras (extra1+extra2) from N. And cheers! that is our answer. Answer= N- extra1-extra2

Note : Practically, either extra1 or extra2 or both will remain 0. But since subtracting 0 does not change the value, we can keep the redundancy.

And we are done! Code it in your favorite Language and keep smiling.

Thank You.