Given an array arr[] of size N,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 the same. Consider zero-based indexing. After printing according to conditions, if remaining, print the remaining elements as it is.
Example 1:
Input: N = 6
arr[] = {1, 2, 3, 4, 5, 6}
Output: 2 1 4 3 6 5
Explanation: Even elements are at 
even position and odd elements are 
at odd position keeping the order 
maintained.
Example 2:
Input: N = 4, arr[] = {3, 2, 4, 1}
Output: 2 3 4 1
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function arrangeOddAndEven() that takes array arr[] and size N as parameters and returns an array according to the above-mentioned condition.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
2 ≤ N ≤ 10^{6}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Starter code:
class Solution:

    def arrangeOddAndEven(self, arr, n):

        # Your code goes here

Solutions:
class Solution:

	def arrangeOddAndEven(self, arr, n):
		e = []
		o = []
		for i in arr:
			if i % 2:
				o.append(i)
			else:
				e.append(i)
		j = 0
		i = 0
		while i < n:
			if j < len(e):
				if j >= len(o):
					arr[i:n] = e[j:len(e)]
					return arr
				arr[i] = e[j]
				i += 1
			if j < len(o):
				if j >= len(e):
					arr[i:n] = o[j:len(o)]
					return arr
				arr[i] = o[j]
				i += 1
			j += 1
		return arr


class Solution:

	def arrangeOddAndEven(self, arr, n):
		p = [0] * n
		(odd, even) = ([], [])
		for elem in arr:
			even.append(elem) if elem % 2 == 0 else odd.append(elem)
		index = 0
		while len(even) or len(odd):
			if index % 2 == 0 and even:
				elem = even.pop(0)
			elif index % 2 == 0:
				elem = odd.pop(0)
			elif index % 2 == 1 and odd:
				elem = odd.pop(0)
			else:
				elem = even.pop(0)
			p[index] = elem
			index += 1
		return p


class Solution:

	def arrangeOddAndEven(self, arr, n):
		even = []
		odd = []
		res = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		while even or odd:
			if len(even):
				res.append(even.pop(0))
			if len(odd):
				res.append(odd.pop(0))
		return res


class Solution:

	def arrangeOddAndEven(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		eind = 0
		oind = 0
		for i in range(n):
			if i % 2 == 0 and eind < len(even) or oind >= len(odd):
				arr[i] = even[eind]
				eind += 1
			elif i % 2 == 1 and oind < len(odd) or eind >= len(even):
				arr[i] = odd[oind]
				oind += 1
		return arr


class Solution:

	def arrangeOddAndEven(self, arr, n):
		o = []
		e = []
		for i in arr:
			if i % 2:
				o.append(i)
			else:
				e.append(i)
		m = min(len(o), len(e))
		for i in range(m):
			arr[2 * i] = e[i]
			arr[2 * i + 1] = o[i]
		if len(o) != len(e):
			if len(o) > len(e):
				arr[m * 2:] = o[m:]
			else:
				arr[m * 2:] = e[m:]
		return arr


class Solution:

	def arrangeOddAndEven(self, arr, n):
		even = []
		odd = []
		ans = []
		for v in arr:
			if v % 2 == 0:
				even.append(v)
			else:
				odd.append(v)
		m = min(len(even), len(odd))
		for i in range(0, m):
			ans.append(even[i])
			ans.append(odd[i])
		return ans + odd[m:] + even[m:]


class Solution:

	def arrangeOddAndEven(self, arr, n):
		even = []
		odd = []
		for i in range(0, len(arr)):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			else:
				odd.append(arr[i])
		i = 0
		j = 0
		comb = []
		j = 1
		for i in odd:
			even.insert(j, i)
			j = j + 2
		return even


class Solution:

	def arrangeOddAndEven(self, arr, N):
		e = []
		o = []
		ans = []
		for i in arr:
			if i % 2 == 0:
				e.append(i)
			else:
				o.append(i)
		i = 0
		j = 0
		while i < len(e) and j < len(o):
			ans.append(e[i])
			ans.append(o[j])
			i += 1
			j += 1
		while i < len(e):
			ans.append(e[i])
			i += 1
		while j < len(o):
			ans.append(o[j])
			j += 1
		return ans


class Solution:

	def arrangeOddAndEven(self, arr, n):
		e = []
		o = []
		for i in range(n):
			if a[i] % 2 == 0:
				e.append(a[i])
			else:
				o.append(a[i])
		i = 0
		j = 0
		ans = []
		t = 0
		while i < len(e) and j < len(o):
			if t % 2 == 0:
				ans.append(e[i])
				i += 1
			else:
				ans.append(o[j])
				j += 1
			t += 1
		while i < len(e):
			ans.append(e[i])
			i += 1
		while j < len(o):
			ans.append(o[j])
			j += 1
		return ans


from collections import deque

class Solution:

	def arrangeOddAndEven(self, arr, n):
		even = deque()
		odd = deque()
		for item in arr:
			if item % 2:
				odd.append(item)
			else:
				even.append(item)
		result = []
		while even and odd:
			result.append(even.popleft())
			result.append(odd.popleft())
		while even:
			result.append(even.popleft())
		while odd:
			result.append(odd.popleft())
		return result


class Solution:

	def arrangeOddAndEven(self, arr, n):
		odd = []
		even = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		i = 0
		j = 0
		k = 0
		while i < len(even) and j < len(odd):
			if k % 2 == 0:
				arr[k] = even[i]
				i += 1
			else:
				arr[k] = odd[j]
				j += 1
			k += 1
		while i < len(even):
			arr[k] = even[i]
			i += 1
			k += 1
		while j < len(odd):
			arr[k] = odd[j]
			j += 1
			k += 1
		return arr


class Solution:

	def arrangeOddAndEven(self, arr, n):
		ev = []
		od = []
		p = []
		for i in arr:
			if i % 2 == 0:
				ev.append(i)
			else:
				od.append(i)
		i = 0
		while ev and od and (i < n):
			if i % 2 == 0 and ev:
				c = ev.pop(0)
				p.append(c)
			else:
				c = od.pop(0)
				p.append(c)
			i += 1
		while ev:
			c = ev.pop(0)
			p.append(c)
		while od:
			c = od.pop(0)
			p.append(c)
		return p


class Solution:

	def arrangeOddAndEven(self, arr, n):
		l = []
		l1 = []
		p = []
		for i in arr:
			if i % 2 == 0:
				l.append(i)
			else:
				l1.append(i)
		while l or l1:
			if len(l):
				p.append(l.pop(0))
			if len(l1):
				p.append(l1.pop(0))
		return p


class Solution:

	def arrangeOddAndEven(self, arr, n):
		odd = []
		even = []
		p = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
		for j in arr:
			if j % 2 != 0:
				odd.append(j)
		while even or odd:
			if len(even):
				p.append(even.pop(0))
			if len(odd):
				p.append(odd.pop(0))
		return p


class Solution:

	def arrangeOddAndEven(self, arr, n):
		k = []
		m = []
		ar = []
		i = 0
		while i < n:
			if arr[i] % 2 == 0:
				k.append(arr[i])
			elif arr[i] % 2 != 0:
				m.append(arr[i])
			i += 1
		for i in range(n):
			if i < len(k):
				ar.append(k[i])
			if i < len(m):
				ar.append(m[i])
		return ar


class Solution:

	def arrangeOddAndEven(self, a, n):
		Odd = []
		even = []
		for i in range(n):
			if a[i] % 2 == 0:
				even.append(a[i])
			else:
				Odd.append(a[i])
		i = 0
		j = 0
		a = []
		while i < len(even) and j < len(Odd):
			a.append(even[i])
			a.append(Odd[j])
			i += 1
			j += 1
		while i < len(even):
			a.append(even[i])
			i += 1
		while j < len(Odd):
			a.append(Odd[j])
			j += 1
		return a


class Solution:

	def arrangeOddAndEven(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		nn = min(len(odd), len(even))
		list2 = []
		ev = 0
		od = 0
		for i in range(nn * 2):
			if i % 2 == 0:
				list2.append(even[ev])
				ev += 1
			else:
				list2.append(odd[od])
				od += 1
		return list2 + odd[nn:] + even[nn:]


import sys

class Solution:

	def arrangeOddAndEven(self, arr, n):
		oddarr = []
		evenarr = []
		for i in arr:
			if i % 2:
				oddarr.append(i)
			else:
				evenarr.append(i)
		infinity = sys.maxsize
		array = []
		k = 0
		x = 0
		while k < len(evenarr) and x < len(oddarr):
			array.append(evenarr[k])
			array.append(oddarr[x])
			k += 1
			x += 1
		if k != len(evenarr):
			while k < len(evenarr):
				array.append(evenarr[k])
				k += 1
		elif x != len(oddarr):
			while x < len(oddarr):
				array.append(oddarr[x])
				x += 1
		return array


class Solution:

	def arrangeOddAndEven(self, arr, n):
		ne = []
		r = []
		for i in range(0, n):
			if arr[i] % 2 == 0:
				r.append(arr[i])
			else:
				ne.append(arr[i])
		arr.clear()
		i = 0
		j = 0
		while i < len(ne) and j < len(r):
			arr.append(r[i])
			arr.append(ne[i])
			i = i + 1
			j = j + 1
		while i < len(r):
			arr.append(r[i])
			i = i + 1
		while j < len(ne):
			arr.append(ne[j])
			j = j + 1
		return arr


class Solution:

	def arrangeOddAndEven(self, arr, n):
		e = []
		o = []
		for x in arr:
			if x % 2 == 0:
				e.append(x)
			else:
				o.append(x)
		res = []
		j = 0
		k = 0
		for i in range(n):
			if i % 2 == 0:
				if j < len(e):
					res.append(e[j])
					j += 1
				else:
					res.append(o[k])
					k += 1
			elif k < len(o):
				res.append(o[k])
				k += 1
			else:
				res.append(e[j])
				j += 1
		return res


class Solution:

	def arrangeOddAndEven(self, arr, n):
		e = []
		o = []
		ans = []
		for i in arr:
			if i % 2 == 0:
				e.append(i)
			else:
				o.append(i)
		l = min(len(e), len(o))
		for i in range(l):
			ans.append(e[i])
			ans.append(o[i])
		for i in e[l:]:
			ans.append(i)
		for i in o[l:]:
			ans.append(i)
		return ans


class Solution:

	def arrangeOddAndEven(self, arr, n):
		odd = []
		eve = []
		for i in arr:
			if i % 2 == 0:
				eve.append(i)
			else:
				odd.append(i)
		(l, eidx, oddidx) = ([], 0, 0)
		nn = min(len(odd), len(eve))
		for i in range(nn * 2):
			if i % 2 == 0:
				l.append(eve[eidx])
				eidx += 1
			else:
				l.append(odd[oddidx])
				oddidx += 1
		return l + eve[nn:] + odd[nn:]


class Solution:

	def arrangeOddAndEven(self, arr, n):
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		j = 0
		res = []
		for i in range(n):
			if i % 2 == 0:
				if even:
					res.insert(i, even.pop(0))
				else:
					res.insert(i, odd.pop(0))
			elif odd:
				res.insert(i, odd.pop(0))
			else:
				res.insert(i, even.pop(0))
		return res


class Solution:

	def arrangeOddAndEven(self, arr, n):
		evenQ = []
		oddQ = []
		for i in range(n):
			if arr[i] % 2 == 0:
				evenQ.append(arr[i])
			else:
				oddQ.append(arr[i])
		for i in range(n):
			if i % 2 == 0:
				if len(evenQ) != 0:
					arr[i] = evenQ.pop(0)
				else:
					arr[i] = oddQ.pop(0)
			elif len(oddQ) != 0:
				arr[i] = oddQ.pop(0)
			else:
				arr[i] = evenQ.pop(0)
		return arr


class Solution:

	def arrangeOddAndEven(self, arr, n):
		l1 = []
		l2 = []
		for i in arr:
			if i % 2 == 0:
				l1.append(i)
			else:
				l2.append(i)
		i = 0
		j = 0
		l = []
		while i < len(l1) or j < len(l2):
			if i < len(l1):
				l.append(l1[i])
				i += 1
			if j < len(l2):
				l.append(l2[j])
				j += 1
		return l


class Solution:

	def arrangeOddAndEven(self, arr, n):
		(even, odd) = ([], [])
		for val in arr:
			if val % 2 == 0:
				even.append(val)
			else:
				odd.append(val)
		res = []
		while even and odd:
			res.append(even.pop(0))
			res.append(odd.pop(0))
		while even:
			res.append(even.pop(0))
		while odd:
			res.append(odd.pop(0))
		return res


class Solution:

	def arrangeOddAndEven(self, arr, n):
		l = []
		l1 = []
		c = 0
		for i in arr:
			if i % 2 == 0:
				l.append(i)
			else:
				l1.append(i)
		i = 0
		j = 1
		while i < n and j < n and (c < len(l1)) and (c < len(l)):
			arr[i] = l[c]
			arr[j] = l1[c]
			i += 2
			j += 2
			c += 1
		if len(l) > len(l1):
			for k in range(c, len(l)):
				arr[i] = l[k]
				i += 1
		elif len(l1) > len(l):
			for k in range(c, len(l1)):
				arr[i] = l1[k]
				i += 1
		return arr


class Solution:

	def arrangeOddAndEven(self, arr, n):
		x = 0
		z = 0
		even = []
		odd = []
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		ans = [0] * len(arr)
		if len(even) >= len(odd):
			for i in range(n):
				if i % 2 == 0:
					ans[i] = even[x]
					x = x + 1
				elif z < len(odd):
					ans[i] = odd[z]
					z = z + 1
				else:
					ans[i] = even[x]
					x = x + 1
		else:
			for i in range(n):
				if i % 2 == 0:
					if x < len(even):
						ans[i] = even[x]
						x = x + 1
					else:
						ans[i] = odd[z]
						z = z + 1
				else:
					ans[i] = odd[z]
					z = z + 1
		return ans