Given an array arr[] of size N, the task is to find the minimum moves to segregate even and odd numbers by swapping two adjacent elements at a time.
Example:
Input: N = 7, arr = {3, 5, 2, 7, 9, 11, 12}
Output: 3
Explanation: Swap arr[2] and arr[3] to get arr = {3, 5, 7, 2, 9, 11, 12}.
Move 2: Swap arr[3] and arr[4] to get arr = {3, 5, 7, 9, 2, 11, 12}.
Move 3: Swap arr[4] and arr[5] to get arr = {3, 5, 7, 9, 11, 2, 12}.
All odds are at the beginning from arr[0 . . . 4]
and evens at the end from arr[5 . . . 6].Input: N = 5, arr = {3, 5, 7, 2, 4}
Output: 0
Approach:
This problem can be broken down into two subproblems:
 Shifting all odd to the front or
 shifting all odd to the end (minimum of which will give us the optimal answer).
So this problem can be solved using the greedy approach, where initially the number of moves to shift odd to the begining are counted and then the number of moves to shift odd to the end are counted and minimum of both is returned as answer.
To shift any number by consecutive swapping, moves required is abs(j – i) where j is the index of the last number of the opposite parity and i is the index of the current number.
Follow the given steps to solve the problem:
 Traverse the array arr from 0 to n1 (say i).
 If arr[i] is odd then add ij in startMoves and increment j.
 Reinitialize j to n1.
 Traverse the array arr from n1 to 0 (say i).
 If arr[i] is odd then add ji to endMoves and decrement j.
 Return minimum of startMoves and endMoves as the final answer.
Below is the implementation of this approach:
C++14

Time Complexity: O(N)
Auxiliary Space: O(1)