Given a sorted deck of cards numbered 1 to N.
1) We pick up 1 card and put it on the back of the deck.
2) Now, we pick up another card, it turns out to be card number 1, we put it outside the deck.
3) Now we pick up 2 cards and put it on the back of the deck.
4) Now, we pick up another card and it turns out to be card numbered 2, we put it outside the deck. ...
We perform this step until the last card.
If such an arrangement of decks is possible, output the arrangement, if it is not possible for a particular value of N then output -1.
Example 1:
Input:
N = 4
Output: 2 1 4 3
Explanation:
We initially have [2 1 4 3]
In Step1, we move the first card to the end. 
Deck now is: [1 4 3 2]
In Step2, we get 1. Hence we remove it. Deck 
now is: [4 3 2]
In Step3, we move the 2 front cards ony by one 
to the end  ([4 3 2] -> [3 2 4] -> [2 4 3]).
Deck now is: [2 4 3]
In Step4, we get 2. Hence we remove it. Deck 
now is: [4 3]
In Step5, the following sequence follows: 
[4 3] -> [3 4] -> [4 3] -> [3 4]. Deck now 
is: [3 4]
In Step6, we get 3. Hence we remove it. Deck 
now is: [4] Finally, we're left with a single 
card and thus, we stop. 
 
Example 2:
Input:
N = 5
Output: 3 1 4 5 2
Your Task:  
You don't need to read input or print anything. Your task is to complete the function rotation() which takes the integer N as input parameters and returns If such arrangement of decks is possible, return the arrangement, if it is not possible for a particular value of n then return -1.
Expected Time Complexity: O(N^2)
Expected Auxiliary Space: O(1)
 
Constraints:
1 ≤ N ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Combinatorics

Data structures

Starter code: #User function Template for python3





class Solution:

    def rotation (self, N):

        # code here

        pass









Solutions:
class Solution:

	def rotation(self, N):
		from collections import deque
		D = deque(range(1, N + 1))
		ans = [0] * N
		p = []
		for i in range(1, N):
			D.rotate(-i)
			p.append(D.popleft())
		p.append(D.pop())
		for (i, v) in enumerate(p, 1):
			ans[v - 1] = i
		return ans


class Solution:

	def rotation(self, N):
		ans = [0] * N
		index = []
		for j in range(N):
			index.append(j)
		ans[1] = 1
		ind = 1
		index.remove(1)
		for j in range(2, N + 1):
			ind = (ind + j) % len(index)
			ans[index[ind]] = j
			index.remove(index[ind])
		return ans


def rotatef(l, t):
	for i in range(t):
		x = l.pop()
		l.insert(0, x)
	return l

class Solution:

	def rotation(self, N):
		lst = []
		for i in range(N, 0, -1):
			lst.insert(0, i)
			lst = rotatef(lst, i)
		return lst


from collections import deque

class Solution:

	def rotation(self, n):
		q = [i for i in range(n)]
		ans = [-1] * n
		for i in range(1, n + 1):
			for j in range(i):
				q.append(q.pop(0))
			ans[q.pop(0)] = i
		return ans


class Solution:

	def rotation(self, N):
		q = []
		while N > 0:
			q.append(N)
			i = 1
			while i <= N:
				q.append(q.pop(0))
				i += 1
			N -= 1
		return q[::-1]


class Solution:

	def rotation(self, N):
		x = []
		x.append(N)
		N -= 1
		while N != 0:
			x.insert(0, N)
			N -= 1
			size = len(x)
			p = x[0]
			rot = p % size
			fp = x[:size - rot]
			lp = x[size - rot:]
			x = lp + fp
		return x


class Solution:

	def rotation(self, N):
		q = [N]
		for i in range(N - 1, 0, -1):
			q.insert(0, i)
			size = len(q)
			rot = i % size
			fp = q[:size - rot]
			lp = q[size - rot:]
			q = lp + fp
		return q


class Solution:

	def rotation(self, n):
		q = [i for i in range(1, n + 1)]
		k = 1
		ans = [0] * (n + 1)
		while k <= n:
			l = k % len(q)
			j = 1
			while j <= l:
				x = q[0]
				q = q[1:]
				q.append(x)
				j += 1
			x = q[0]
			q = q[1:]
			ans[x] = k
			k += 1
		return ans[1:]


class Solution:

	def rotation(self, N):
		ans = []
		arr = [0] * N
		q = []
		for i in range(0, N):
			q.append(i)
		i = 1
		while len(q) != 0:
			j = 0
			while j < i:
				x = q.pop(0)
				q.append(x)
				j += 1
			loc = q[0]
			arr[loc] = i
			q.pop(0)
			i += 1
		for i in range(0, N):
			ans.append(arr[i])
		return ans


class Solution:

	def rotation(self, n):
		q = []
		for i in range(1, n + 1):
			q.append(i)
		ans = [0] * (n + 1)
		for i in range(1, n + 1):
			rot = i % (n - i + 1)
			while rot is not 0:
				f = q.pop(0)
				q.append(f)
				rot -= 1
			idx = q.pop(0)
			ans[idx] = i
		ans.pop(0)
		return ans


class Solution:

	def rotation(self, N):
		arr = [0] * 1001
		q = [i for i in range(1, N + 1)]
		i = 1
		while len(q):
			j = 0
			while i > j:
				x = q.pop(0)
				q.append(x)
				j += 1
			x = q.pop(0)
			if arr[x] != 0:
				return [-1]
			arr[x] = i
			i += 1
		return arr[1:N + 1]


class Solution:

	def rotation(self, n):
		from collections import deque
		order = [0 for i in range(n)]
		q = deque([i for i in range(n)])
		c = 1
		while len(q) > 1:
			for i in range(c):
				q.append(q.popleft())
			order[q.popleft()] = c
			c += 1
		order[q.popleft()] = c
		return order
		pass


class Solution:

	def rotation(self, n):
		order = [0 for i in range(n)]
		c = 1
		cl = n
		j = 0
		for i in range(1, n + 1):
			cnt = 0
			while cnt < c:
				if order[j]:
					j += 1
					j %= n
				else:
					cnt += 1
					j += 1
					j %= n
			while order[j]:
				j += 1
				j %= n
			order[j] = i
			c += 1
		return order
		pass


class Solution:

	def rotation(self, n):
		ar = [str(i) for i in range(1, n + 1)]
		for i in range(n - 1, 0, -1):
			for j in range(i):
				temp = ar.pop()
				ar.insert(i - 1, temp)
		return ar


from itertools import permutations

class Solution:

	def rotation(self, n):
		li = []
		for i in range(n):
			li.append(0)
		p = 0
		for i in range(1, n):
			k = i
			while k:
				if li[p] == 0:
					k -= 1
				p += 1
				if p > n - 1:
					p = li.index(0)
			if li[p] == 0:
				li[p] = i
			else:
				while li[p] != 0:
					p += 1
					if p > n - 1:
						p = li.index(0)
				li[p] = i
		p = li.index(0)
		li[p] = n
		return li


from collections import deque

class Solution:

	def rotation(self, N):
		ans = [0] * N
		ref = deque([i for i in range(1, N + 1)])
		for i in range(1, N + 1):
			j = i
			while j != 0:
				a = ref.popleft()
				ref.append(a)
				j = j - 1
			a = ref.popleft()
			ans[a - 1] = i
		return ans


class Solution:

	def rotation(self, N):
		t = []
		for i in range(N, 0, -1):
			t = [i] + t
			size = len(t)
			rot = i % size
			m = size - rot
			t = t[m:] + t[:m]
		return t


class Solution:

	def rotation(self, N):
		cards = [N]
		for i in range(N - 1, 0, -1):
			cards = self.add_card(cards, i)
		return cards

	def add_card(self, current, m):
		target = [m] + current
		new = self.shuffle(target, m)
		return new

	@staticmethod
	def shuffle(arr, k):
		for i in range(k):
			arr = arr[-1:] + arr[:-1]
		return arr


class Solution:

	def rotation(self, N):
		arr = [0] * N
		t = [0] * N
		i = 0
		num = 1
		while True:
			cnt = 0
			while cnt < num:
				i = (i + 1) % N
				if t[i] == 0:
					cnt += 1
			t[i] = -1
			arr[i] = num
			num += 1
			if num == N + 1:
				break
			while t[i] != 0:
				i = (i + 1) % N
		return arr


class Solution:

	def rotation(self, N):
		ans = []
		for i in range(N, 0, -1):
			ans = [i] + ans
			for j in range(i):
				popped = ans.pop(-1)
				ans = [popped] + ans
		return ans


class Solution:

	def rotation(self, n):
		L = list(range(1, n + 1))
		A = [0 for i in range(n)]
		K = 1
		count = 1
		while len(L):
			for _ in range(count):
				x = L.pop(0)
				L.append(x)
			Index = L.pop(0)
			A[Index - 1] = K
			K += 1
			count += 1
		return A


class Solution:

	def rotation(self, N):
		result = [0 for _ in range(N)]
		current_index = -1
		for i in range(1, N + 1):
			count = 0
			while True:
				current_index = (current_index + 1) % N
				if count == i and result[current_index] == 0:
					count = 0
					result[current_index] = i
					break
				elif count < i and result[current_index] == 0:
					count += 1
		return result