Join Us
Loading Similar Posts
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?
http://thejoboverflow.com/p/p31/#p89
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.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).