Reputation: 4820
Interview question: Even and odd elements at even and odd positions (keep elements order)
The following question asked in an interview:
Given an array. The task is to arrange the array such that:
- odd elements occupy the odd positions and even elements occupy the even positions.
- The order of elements must remain same.
- Consider zero-based indexing.
- After printing according to conditions, if remaining, print the remaining elements as it is.
Example:
Input: Arr = 2, 4, 6, 8, 10, 1, 3, 5, 7, 9
Output: Arr= 2,1,4,3,6,5,8,7,10,9
Is there a solution with no constant space (i.e O(1)) and in O(N) time ?
Upvotes: 1
Views: 1206
Answers (1)
Reputation: 92
If there's n/2 even elements and n/2 odd elements the solution can be very simple, keep an 'even pointer' and 'odd pointer' to the first even empty place in the new array, and the first odd empty place at the new array. than just go over the old array, fill elements at the right position, and don't forget to increase the pointer by 2; If the number of odd elements is diffrenet than the even ones- u can disocover how much even and odd numners are at O(n), so again, the question is quite simple.
Upvotes: 0
Related Questions
- Arrange odd numbers first, followed by even number. order of odd even should not be changed
- Array even & odd sorting
- O(1) space complexity for odd-even
- Odd elements at odd and even elements at even position
- Finding EVEN number of times repeating integer in an array where rest of the integers repeat ODD number of times
- Algorithm: array with odd and even numbers
- Which is most efficient method for processing odd and even elements?
- move all even numbers on the first half and odd numbers to the second half in an integer array
- Segregate even and odd places of an array in O(N) time and O(1) space
- Rearrange even and odd in an array