Question: Rearrange Elements (Paytm Coding Round Problem)
2
Entering edit mode

<h2>Problem Statement</h2> Rearrange array such that all odd numbers occupy odd positions and even numbers occupy even position. Order of numbers needs to be maintained without use of extra space.<br> Note: Take 0-based indexing here.

<h3>Constraints</h3>

<ul> <li>Array size (N) <=10<sup>5</sup></li> <li>N must be even here.</li> <li>Exactly N/2 even numbers are present in the array.</li> <li>Exactly N/2 odd numbers are present in the array.</li> </ul>

<br><br> Example:<br> arr[] = {1, 3, 42, 17, 31, 21, 2, 4, 12, 84};<br><br>

Output: <br> arr[] = {42, 1, 2, 3, 4, 17, 12, 31, 84, 21};<br><br>

How we implement this with O(N) time complexity and O(1) space complexity?

Entering edit mode
3
Problem/Solution is very similar to this problem linked at TJO
http://thejoboverflow.com/p/p31/#p89
1.4k
Entering edit mode
2
Observation: For every number, you know its exact position in the modified array.At first, we think that maintaining order is an unnecessary evil but that is what makes it possible to rearrange the array in O(N), O(1).Please go through the comment below.
vaibhavr
• 370
Entering edit mode
2
Well framed, but its not entirely correct. There are ample of ways, to solve problem if we lift condition of "mantaining order".
Consider this algo for example A={2,3,1,5,4}. A has two independent cycles of length 3 (2->3->1) and of length 2 (5->4). For each cycle we simply start from any one number and put it to its correct place, and take integer present in its correct place and put that to its correct place and so on. This is also a valid solution with O(N), O(1).