Given an array arr[] of size N containing equal number of odd and even numbers. Arrange the numbers in such a way that all the even numbers get the even index and odd numbers get the odd index.
Note: There are multiple possible solutions, Print any one of them. Also, 0-based indexing is considered.
 
Example 1:
Input:
N = 6
arr[] = {3, 6, 12, 1, 5, 8}
Output:
1
Explanation:
6 3 12 1 8 5 is a possible solution.
The output will always be 1 if your
rearrangement is correct.
Example 2:
Input:
N = 4
arr[] = {1, 2, 3, 4}
Output :
1
Your Task:  
You don't need to read input or print anything. Your task is to complete the function reArrange() which takes an integer N and an array arr of size N as input and reArranges the array in Place without any extra space.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

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

Starter code:
#User function Template for python3

class Solution:
    def reArrange(self, arr, N):
        # code here 

Solutions:
class Solution:

	def reArrange(self, arr, N):
		evenIndex = 0
		oddIndex = 1
		while evenIndex < N and oddIndex < N:
			if arr[evenIndex] % 2 != 0 and arr[oddIndex] % 2 == 0:
				temp = arr[evenIndex]
				arr[evenIndex] = arr[oddIndex]
				arr[oddIndex] = temp
			else:
				if arr[evenIndex] % 2 == 0:
					evenIndex += 2
				if arr[oddIndex] % 2 != 0:
					oddIndex += 2


class Solution:

	def reArrange(self, arr, N):
		odd_idx = 1
		even_idx = 0
		while odd_idx < len(arr) and even_idx < len(arr):
			if arr[odd_idx] % 2 == 0 and arr[even_idx] % 2 != 0:
				(arr[odd_idx], arr[even_idx]) = (arr[even_idx], arr[odd_idx])
			if arr[odd_idx] % 2 != 0:
				odd_idx += 2
			if arr[even_idx] % 2 == 0:
				even_idx += 2
		return 1


class Solution:

	def reArrange(self, arr, N):
		a = [0] * len(arr)
		odd_idx = 1
		even_idx = 0
		for i in arr:
			if i % 2 == 0:
				a[even_idx] = i
				even_idx += 2
			else:
				a[odd_idx] = i
				odd_idx += 2
		for (i, x) in enumerate(a):
			arr[i] = x
		return 1


class Solution:

	def reArrange(self, arr, N):
		oddInd = 1
		evenInd = 0
		while True:
			while evenInd < N and arr[evenInd] % 2 == 0:
				evenInd += 2
			while oddInd < N and arr[oddInd] % 2 == 1:
				oddInd += 2
			if evenInd < N and oddInd < N:
				(arr[evenInd], arr[oddInd]) = (arr[oddInd], arr[evenInd])
			else:
				break


class Solution:

	def reArrange(self, arr, N):
		l1 = []
		l2 = []
		for i in arr:
			if i % 2 == 0:
				l1.append(i)
			else:
				l2.append(i)
		k = 0
		for i in range(0, N, 2):
			arr[i] = l1[i // 2]
		for i in range(1, N, 2):
			arr[i] = l2[i // 2]
		return arr


class Solution:

	def reArrange(self, arr, N):
		i = 0
		j = 1
		while True:
			while i < N and arr[i] % 2 == 0:
				i += 2
			while j < N and arr[j] % 2 == 1:
				j += 2
			if i < N and j < N:
				temp = arr[i]
				arr[i] = arr[j]
				arr[j] = temp
			else:
				break


class Solution:

	def reArrange(self, arr, N):
		e = 0
		o = 1
		while e < N and o < N:
			if arr[e] % 2 != 0 and arr[o] % 2 != 1:
				(arr[o], arr[e]) = (arr[e], arr[o])
				e = e + 2
				o = o + 2
			elif arr[e] % 2 != 0 and arr[o] % 2 == 1:
				o = o + 2
			elif arr[o] % 2 != 1 and arr[e] % 2 == 0:
				e = e + 2
			elif arr[e] % 2 == 0 and arr[o] % 2 == 1:
				e = e + 2
				o = o + 2


class Solution:

	def reArrange(self, arr, N):
		le = []
		lo = []
		for i in arr:
			if i % 2 == 0:
				le.append(i)
			else:
				lo.append(i)
		ej = oj = 0
		for i in range(N):
			if i % 2 == 0:
				arr[i] = le[ej]
				ej += 1
			else:
				arr[i] = lo[oj]
				oj += 1
		return arr


class Solution:

	def reArrange(self, arr, N):
		c = []
		d = []
		for i in arr:
			if i % 2 == 0:
				c.append(i)
			else:
				d.append(i)
		l = 0
		m = 0
		for i in range(N):
			if i % 2 == 0:
				arr[i] = c[l]
				l += 1
			else:
				arr[i] = d[m]
				m += 1


class Solution:

	def reArrange(self, arr, N):
		e = []
		o = []
		l = []
		for i in arr:
			if i % 2 == 0:
				e.append(i)
			else:
				o.append(i)
		j = 0
		k = 0
		for i in range(N):
			if i % 2 == 0:
				arr[i] = e[j]
				j += 1
			else:
				arr[i] = o[k]
				k += 1


class Solution:

	def reArrange(self, arr, N):
		(even, odd) = ([], [])
		for elem in arr:
			even.append(elem) if elem % 2 == 0 else odd.append(elem)
		arr[::2] = even
		arr[1::2] = odd


class Solution:

	def reArrange(self, arr, N):
		mew = arr[:]
		arr.clear()
		(even, odd) = ([], [])
		for i in mew:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		for i in range(N // 2):
			arr.append(even[i])
			arr.append(odd[i])


class Solution:

	def reArrange(self, arr, N):
		n = len(arr)
		hashtable = {'even': [], 'odd': []}
		for i in arr:
			if i % 2 == 0:
				hashtable['even'].append(i)
			else:
				hashtable['odd'].append(i)
		arr.clear()
		for i in range(n):
			if i % 2 == 0:
				arr.append(hashtable['even'].pop())
			else:
				arr.append(hashtable['odd'].pop())
		return arr


class Solution:

	def reArrange(self, arr, N):
		l1 = []
		l2 = []
		for i in arr:
			if i % 2 == 0:
				l1.append(i)
			else:
				l2.append(i)
		t1 = 0
		t2 = 0
		for i in range(N):
			if i % 2 == 0 or i == 0:
				arr[i] = l1[t1]
				t1 += 1
			else:
				arr[i] = l2[t2]
				t2 += 1


class Solution:

	def reArrange(self, arr, N):
		(v, k) = ([], [])
		for i in arr:
			if i % 2 == 0:
				v.append(i)
			else:
				k.append(i)
		(j, l) = (0, 0)
		for i in range(N):
			if i % 2 == 0:
				arr[i] = v[j]
				j += 1
			else:
				arr[i] = k[l]
				l += 1
		return arr


class Solution:

	def reArrange(self, arr, N):
		i = 0
		j = 1
		if N == 1 or N % 2 == 1:
			return
		while i < N and j < N:
			if not i % 2:
				if arr[i] % 2 == 0:
					i += 2
			if j % 2:
				if arr[j] % 2:
					j += 2
			if i < N and j < N:
				(arr[i], arr[j]) = (arr[j], arr[i])
		return


class Solution:

	def reArrange(self, arr, N):
		k = []
		even = [i for i in arr if i % 2 == 0]
		odd = [i for i in arr if i % 2 == 1]
		for i in range(len(even)):
			k.append(even[i])
			k.append(odd[i])
		arr[:] = k[:]


class Solution:

	def reArrange(self, arr, N):
		odd = []
		even = []
		res = []
		j = 0
		for i in arr:
			if i % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		while j < N:
			if j % 2:
				res.append(odd.pop())
			else:
				res.append(even.pop())
			j += 1
		arr[:] = res


class Solution:

	def reArrange(self, arr, N):
		j = 0
		k = 1
		while k < N and j < N:
			if j % 2 == 0 and arr[j] % 2 == 0:
				j += 2
			elif k % 2 == 1 and arr[k] % 2 == 1:
				k += 2
			else:
				(arr[k], arr[j]) = (arr[j], arr[k])
				k += 2
				j += 2


class Solution:

	def reArrange(self, arr, n):
		e = 0
		h = 1
		while e < n and h < n:
			if arr[e] % 2 == 0:
				e += 2
			elif arr[h] % 2 != 0:
				h += 2
			else:
				(arr[e], arr[h]) = (arr[h], arr[e])


class Solution:

	def reArrange(self, arr, N):
		e = 0
		o = 1
		for i in range(N - 1):
			if arr[e] % 2 == 0:
				e += 2
			if arr[o] % 2 != 0:
				o += 2
			if e >= N or o >= N:
				break
			if arr[e] % 2 != 0 and arr[o] % 2 == 0:
				(arr[e], arr[o]) = (arr[o], arr[e])


class Solution:

	def reArrange(self, arr, N):
		odd_index = 0
		even_index = 1
		while True:
			while odd_index < N and arr[odd_index] % 2 == 0:
				odd_index += 2
			while even_index < N and arr[even_index] % 2 == 1:
				even_index += 2
			if odd_index < N and even_index < N:
				(arr[odd_index], arr[even_index]) = (arr[even_index], arr[odd_index])
			else:
				break
		return arr


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def reArrange(self, arr, N):
		e = 0
		o = 1
		for i in range(len(arr)):
			if arr[e] % 2 == 0:
				e += 2
			if arr[o] % 2 != 0:
				o += 2
			if e >= len(arr) or o >= len(arr):
				break
			else:
				(arr[e], arr[o]) = (arr[o], arr[e])
		return arr


class Solution:

	def reArrange(self, arr, N):
		if len(arr) <= 1:
			return arr
		even = 0
		odd = 1
		while even < len(arr) and odd < len(arr):
			if arr[even] % 2 == 0 and arr[odd] % 2 != 0:
				even += 2
				odd += 2
			elif arr[even] % 2 != 0 and arr[odd] % 2 == 0:
				(arr[even], arr[odd]) = (arr[odd], arr[even])
				even += 2
				odd += 2
			elif arr[even] % 2 == 0 and arr[odd] % 2 == 0:
				even += 2
			elif arr[even] % 2 != 0 and arr[odd] % 2 != 0:
				odd += 2
		return arr


class Solution:

	def reArrange(self, arr, N):
		(i, j) = (0, 1)
		ans = 0
		while i < N and j < N:
			while i < N and arr[i] & 1 == 0:
				i += 2
			while j < N and arr[j] & 1 == 1:
				j += 2
			if i < N and j < N:
				(arr[i], arr[j]) = (arr[j], arr[i])
				ans += 1
			i += 2
			j += 2
		return ans


class Solution:

	def reArrange(self, arr, n):
		(mo, me) = (1, 0)
		while True:
			while me < n and arr[me] % 2 == 0:
				me += 2
			while mo < n and arr[mo] % 2 != 0:
				mo += 2
			if mo < n and me < n:
				(arr[mo], arr[me]) = (arr[me], arr[mo])
			else:
				break


class Solution:

	def reArrange(self, arr, N):
		(start, mo, me) = (0, [], [])
		while start < N:
			if start % 2 == 0 and arr[start] % 2 != 0:
				if me:
					tmp = me.pop()
					(arr[start], arr[tmp]) = (arr[tmp], arr[start])
				else:
					mo.append(start)
			elif start % 2 != 0 and arr[start] % 2 == 0:
				if mo:
					tmp = mo.pop()
					(arr[start], arr[tmp]) = (arr[tmp], arr[start])
				else:
					me.append(start)
			start += 1


class Solution:

	def reArrange(self, arr, N):
		od = []
		ev = []
		for x in range(N):
			if x & 1 == 1:
				if arr[x] & 1 == 0:
					if od != []:
						i = od.pop()
						(arr[i], arr[x]) = (arr[x], arr[i])
					else:
						ev.append(x)
			elif arr[x] & 1 == 1:
				if ev != []:
					i = ev.pop()
					(arr[i], arr[x]) = (arr[x], arr[i])
				else:
					od.append(x)


class Solution:

	def reArrange(self, arr, N):
		lst1 = []
		lst2 = []
		a = 0
		b = 0
		for i in range(N):
			if arr[i] % 2 == 0:
				lst1.append(arr[i])
			else:
				lst2.append(arr[i])
		for i in range(0, N):
			if i % 2 == 0:
				arr[i] = lst1[a]
				a = a + 1
			else:
				arr[i] = lst2[b]
				b = b + 1


class Solution:

	def reArrange(self, arr, N):
		el = 0
		oh = 1
		while el < N and oh < N:
			if arr[el] % 2 == 0:
				el += 2
			elif arr[oh] % 2 != 0:
				oh += 2
			else:
				(arr[el], arr[oh]) = (arr[oh], arr[el])


class Solution:

	def reArrange(self, arr, N):
		mydict = {'even': [], 'odd': []}
		for i in arr:
			if i % 2 == 0:
				mydict['even'].append(i)
			else:
				mydict['odd'].append(i)
		arr.clear()
		for i in range(N):
			if i % 2 == 0:
				arr.append(mydict['even'].pop())
			else:
				arr.append(mydict['odd'].pop())
		return arr


class Solution:

	def reArrange(self, arr, N):
		(i, j, k) = (0, 1, 0)
		while k < N and i < N and (j < N):
			if arr[k] % 2 == 0:
				(arr[k], arr[i]) = (arr[i], arr[k])
				i += 2
				k = min(i, j)
			else:
				(arr[k], arr[j]) = (arr[j], arr[k])
				j += 2
				k = min(i, j)
		return arr


class Solution:

	def reArrange(self, arr, N):
		even = 0
		odd = 1
		while True:
			while even < N and arr[even] % 2 == 0:
				even += 2
			while odd < N and arr[odd] % 2 == 1:
				odd += 2
			if even < N and odd < N:
				(arr[even], arr[odd]) = (arr[odd], arr[even])
			else:
				break


class Solution:

	def reArrange(self, arr, N):
		(even, odd) = (0, 1)
		while even < N and odd < N:
			if arr[even] % 2 != 0 and arr[odd] % 2 == 0:
				(arr[even], arr[odd]) = (arr[odd], arr[even])
				even += 2
				odd += 2
			elif arr[even] % 2 == 0 and arr[odd] % 2 == 0:
				even += 2
			else:
				odd += 2


class Solution:

	def reArrange(self, arr, n):
		b = []
		c = []
		for i in arr:
			if i % 2 == 0:
				b.append(i)
			else:
				c.append(i)
		i = 0
		j = 0
		while i < n - 1:
			arr[i] = b[j]
			arr[i + 1] = c[j]
			i += 2
		return arr


class Solution:

	def reArrange(self, a, n):
		i = 0
		j = 1
		while i < n and j < n:
			if a[i] % 2 == 0:
				i += 2
			elif a[j] % 2 == 1:
				j += 2
			else:
				(a[i], a[j]) = (a[j], a[i])


class Solution:

	def reArrange(self, arr, N):
		even_index = 0
		odd_index = 1
		while even_index < N and odd_index <= N:
			if arr[even_index] % 2 == 0:
				even_index += 2
			elif arr[odd_index] % 2 == 1:
				odd_index += 2
			else:
				(arr[even_index], arr[odd_index]) = (arr[odd_index], arr[even_index])
				even_index += 2
				odd_index += 2


class Solution:

	def reArrange(self, arr, N):
		newArr = arr.copy()
		j = 0
		k = 1
		for i in range(N):
			if newArr[i] % 2 == 0:
				arr[j] = newArr[i]
				j += 2
			else:
				arr[k] = newArr[i]
				k += 2


class Solution:

	def reArrange(self, arr, N):
		odd = []
		even = []
		result = []
		for item in arr:
			if item % 2:
				odd.append(item)
			else:
				even.append(item)
		i = 0
		on = len(odd)
		en = len(even)
		while True:
			result.append(even[i])
			if i == on:
				break
			result.append(odd[i])
			i += 1
			if i == en:
				break
		for i in range(N):
			arr[i] = result[i]


class Solution:

	def reArrange(self, arr, N):
		even = []
		odd = []
		for i in range(len(arr)):
			if arr[i] % 2 == 0:
				even.append(arr[i])
			else:
				odd.append(arr[i])
		ans = []
		i = 0
		while i < N // 2:
			ans.append(even[i])
			ans.append(odd[i])
			i += 1
		for i in range(N):
			arr[i] = ans[i]
		return arr


class Solution:

	def reArrange(self, arr, N):
		evl = 0
		odl = 1
		while evl < N and odl < N:
			if arr[evl] % 2 == 0:
				evl += 2
			elif arr[odl] % 2 != 0:
				odl += 2
			else:
				(arr[evl], arr[odl]) = (arr[odl], arr[evl])
				evl += 2
				odl += 2


class Solution:

	def reArrange(self, arr, N):
		ev = []
		od = []
		for i in arr:
			if i % 2 == 0:
				ev.append(i)
			else:
				od.append(i)
		k = 0
		for i in range(N):
			if i % 2 == 0:
				arr[i] = ev[k]
			else:
				arr[i] = od[k]
			k = int(i / 2)


class Solution:

	def reArrange(self, arr, n):
		i = 0
		j = 1
		(a, b) = ([], [])
		for k in range(n):
			if arr[k] % 2 == 0:
				a.append(arr[k])
			else:
				b.append(arr[k])
		for k in range(n // 2):
			arr[i] = a[k]
			arr[j] = b[k]
			i += 2
			j += 2


class Solution:

	def reArrange(self, arr, N):
		i = 0
		j = 1
		while i < N:
			if arr[i] % 2:
				(arr[i], arr[j]) = (arr[j], arr[i])
				j += 2
			else:
				i += 2


class Solution:

	def reArrange(self, arr, N):
		arr1 = []
		arr2 = []
		for i in range(N):
			if arr[i] % 2 == 0:
				arr1.append(arr[i])
			else:
				arr2.append(arr[i])
		i = 0
		for ele in arr1:
			arr[i] = ele
			i += 2
		j = 1
		for ele in arr2:
			arr[j] = ele
			j += 2
		return arr


class Solution:

	def reArrange(self, arr, N):
		even = 0
		odd = 1
		while even < N and arr[even] % 2 == 0:
			even += 2
		while odd < N and arr[odd] % 2 != 0:
			odd += 2
		while even < N and odd < N:
			temp = arr[even]
			arr[even] = arr[odd]
			arr[odd] = temp
			while even < N and arr[even] % 2 == 0:
				even += 2
			while odd < N and arr[odd] % 2 != 0:
				odd += 2


class Solution:

	def reArrange(self, arr, N):
		i = 0
		j = 1
		while i < len(arr) and j < len(arr):
			if arr[i] % 2 == 0 and i % 2 == 0:
				i += 2
				continue
			if arr[j] % 2 != 0 and j % 2 != 0:
				j += 2
				continue
			(arr[i], arr[j]) = (arr[j], arr[i])


class Solution:

	def reArrange(self, arr, N):
		dict = {}
		even = 0
		odd = 1
		result = [0] * len(arr)
		for element in arr:
			if element % 2 == 0:
				result[even] = element
				even += 2
			else:
				result[odd] = element
				odd += 2
		for i in range(len(result)):
			arr[i] = result[i]


class Solution:

	def reArrange(self, arr, N):
		l1 = []
		l2 = []
		l3 = []
		for i in arr:
			if i % 2 == 0:
				l1.append(i)
			else:
				l2.append(i)
		for i in range(len(l1)):
			l3.append(l1[i])
			l3.append(l2[i])
		arr[:] = l3[:]
		return arr


class Solution:

	def reArrange(self, arr, n):
		a = []
		b = []
		c = []
		for i in arr:
			if i % 2 == 0:
				a.append(i)
				continue
			else:
				b.append(i)
				continue
		for i in range(0, n):
			if i % 2 == 0:
				arr[i] = a[i // 2]
			else:
				arr[i] = b[i // 2]
		return arr


class Solution:

	def reArrange(self, arr, N):
		k = []
		lis = []
		res = []
		for i in range(N):
			if arr[i] % 2 == 0:
				k.append(arr[i])
			else:
				lis.append(arr[i])
		for i in range(len(lis)):
			res.append(k[i])
			res.append(lis[i])
		for i in range(N):
			arr[i] = res[i]
		return arr


class Solution:

	def reArrange(self, arr, N):
		A = []
		B = []
		for i in arr:
			if i % 2 == 0:
				A.append(i)
			else:
				B.append(i)
		for i in range(N // 2):
			arr.append(A[i])
			arr.append(B[i])
		arr[:] = arr[N:]
		return arr


class Solution:

	def reArrange(self, arr, N):
		ar1 = []
		ar2 = []
		for e in arr:
			if e % 2 == 0:
				ar2.append(e)
			else:
				ar1.append(e)
		j = 0
		for i in range(0, len(ar1)):
			arr[j] = ar2[i]
			j = j + 1
			arr[j] = ar1[i]
			j = j + 1
		return arr


class Solution:

	def reArrange(self, arr, N):
		x = 0
		y = 1
		while True:
			while x < N and arr[x] % 2 == 0:
				x += 2
			while y < N and arr[y] % 2 == 1:
				y += 2
			if x < N and y < N:
				temp = arr[x]
				arr[x] = arr[y]
				arr[y] = temp
			else:
				break
		return arr


class Solution:

	def reArrange(self, arr, N):
		o = 1
		e = 0
		p = 0
		while 1:
			while e < N and arr[e] % 2 == 0:
				e += 2
			while o < N and arr[o] % 2 != 0:
				o += 2
			if e < N and o < N:
				p = arr[e]
				arr[e] = arr[o]
				arr[o] = p
			else:
				break


class Solution:

	def reArrange(self, arr, N):
		a = []
		b = []
		for i in range(N):
			if arr[i] % 2 == 0:
				a.append(arr[i])
			else:
				b.append(arr[i])
		j = 0
		i = 0
		while i < N and j < N:
			if i < N:
				arr[i] = a[j]
				i += 1
				arr[i] = b[j]
				i += 1
				j += 1
		return arr