Given an integer n. Print first n elements of Recaman’s sequence.
It is basically a function with domain and co-domain as natural numbers and 0. It is recursively defined as below:
Specifically, let a(n) denote the (n+1)-th term. (0 being already there).
The rule says:
a(0) = 0
a(n) = a(n-1) - n      if a(n-1) - n > 0 and is not already present in the sequence
       =  a(n-1) + n    otherwise. 
Example 1:
Input: n = 6
Output: 0 1 3 6 2 7
Explaination: Follow the rule and this 
will be the output.
Example 2:
Input: n = 3
Output: 0 1 3
Explaination: If the rule is followed, 
it will produce this output.
Your Task:
You do not need to read input or print anything. Your task is to complete the function recamanSequence() which takes n as the input parameter and returns the sequence.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n ≤ 100

Difficulty: EASY
Tags: String algorithms

Data structures

Mathematics

Complete search
Skill types: Data structures

Complete search
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3

class Solution:
    def recamanSequence(self, n):
        # code here

Solutions:
class Solution:

	def __init__(self):
		self.res = []

	def recamanSequence(self, n):
		self.recaman(n)
		return self.res

	def recaman(self, n):
		if n == 1:
			self.res.append(0)
			return 0
		self.recaman(n - 1)
		minus_val = self.res[-1] - (n - 1)
		if minus_val > 0 and minus_val not in self.res:
			self.res.append(minus_val)
		else:
			self.res.append(self.res[-1] + (n - 1))


class Solution:

	def recamanSequence(self, n):
		ans = [0]
		self.helper(n, ans)
		return ans

	def helper(self, n, ans):
		if n == 0:
			return
		self.helper(n - 1, ans)
		if ans[n - 1] - n > 0 and ans[n - 1] - n not in ans:
			ans.append(ans[n - 1] - n)
		else:
			ans.append(ans[n - 1] + n)


class Solution:

	def recamanSequence(self, n):
		a = []
		if n == 0:
			return [0]
		return self.sol(n - 1, a)

	def sol(self, n, a):
		if n == 0:
			a.append(n)
			return a
		self.sol(n - 1, a)
		if a[n - 1] - n > 0 and a[n - 1] - n not in a:
			a.append(a[n - 1] - n)
		else:
			a.append(a[n - 1] + n)
		return a


class Solution:

	def findSeq(self, i, n, seq):
		if i == n:
			return
		curr = seq[i - 1] - i
		if curr not in seq:
			if curr > 0:
				seq.append(curr)
			else:
				curr = seq[i - 1] + i
				seq.append(curr)
		else:
			curr = seq[i - 1] + i
			seq.append(curr)
		self.findSeq(i + 1, n, seq)

	def recamanSequence(self, n):
		seq = [0]
		self.findSeq(1, n, seq)
		return seq


class Solution:

	def recamanSequence(self, n):
		if n == 1:
			return [0]
		s = []
		arr = [0] * n
		arr[0] = 0
		s.append(arr[0])
		for i in range(1, n):
			curr = arr[i - 1] - i
			for j in range(0, i):
				if arr[j] == curr or curr < 0:
					curr = arr[i - 1] + i
					break
			arr[i] = curr
			s.append(arr[i])
		return s


class Solution:

	def recamanSequence(self, n):
		res = [0]
		i = 1
		while i < n:
			x = res[i - 1] - i
			if x > 0 and x not in res:
				res.append(x)
			else:
				res.append(res[i - 1] + i)
			i += 1
		return res


class Solution:

	def recamanSequence(self, n):
		a = [0]
		self.rec(n, a)
		return a

	def rec(self, n, ans):
		if n == 0:
			return
		self.rec(n - 1, ans)
		if ans[n - 1] - n > 0 and ans[n - 1] - n not in ans:
			ans.append(ans[n - 1] - n)
		else:
			ans.append(ans[n - 1] + n)


class Solution:

	def recur(self, n, li):
		if n == 0:
			return
		self.recur(n - 1, li)
		if li[n - 1] - n > 0 and li[n - 1] - n not in li:
			li.append(li[n - 1] - n)
		else:
			li.append(li[n - 1] + n)

	def recamanSequence(self, n):
		li = [0]
		self.recur(n, li)
		return li


class Solution:

	def recamanSequence(self, n):
		ans = [0]
		for i in range(1, n):
			if ans[i - 1] - i > 0 and ans[i - 1] - i not in ans:
				ans.append(ans[i - 1] - i)
			else:
				ans.append(ans[i - 1] + i)
		return ans


sequence = [0]
setti = set([0])

class Solution:

	def recamanSequence(self, n):
		while len(sequence) < n:
			i = len(sequence)
			next = sequence[-1] - i
			if next <= 0 or next in setti:
				next += i * 2
			sequence.append(next)
			setti.add(next)
		return sequence[:n]


class Solution:

	def recamanSequence(self, n):
		ans = [0]
		s = set()
		s.add(0)
		for i in range(1, n):
			c = ans[-1] - i
			if c > 0 and c not in s:
				ans.append(c)
				s.add(c)
			else:
				t = ans[-1] + i
				ans.append(t)
				s.add(t)
		return ans


class Solution:

	def recamanSequence(self, n):
		dp = [0] * n
		s = set()
		s.add(0)
		for i in range(1, n):
			val = dp[i - 1] - i
			if val not in s and val > 0:
				dp[i] = val
			else:
				dp[i] = dp[i - 1] + i
			s.add(dp[i])
		return dp


class Solution:

	def recamanSequence(self, n):
		ds = [0 for i in range(n)]

		def help(ds, i):
			if i >= n:
				return
			val = ds[i - 1] - i
			if val > 0 and val not in ds:
				ds[i] = val
			else:
				ds[i] = val + 2 * i
			help(ds, i + 1)
		help(ds, 1)
		return ds


class Solution:

	def recamanSequence(self, n):
		ds = []

		def helper(n, ds):
			if n == 1:
				ds.append(0)
				ds.append(n)
				return n
			value = helper(n - 1, ds)
			if value - n > 0 and value - n not in ds:
				ds.append(value - n)
				return value - n
			else:
				ds.append(value + n)
				return value + n
		helper(n, ds)
		return ds


class Solution:

	def recamanSequence(self, n):
		l = [0]
		l1 = []
		for i in range(1, n):
			a = l[i - 1] - i
			if a > 0 and a not in l:
				l.append(a)
			else:
				a = l[i - 1] + i
				l.append(a)
		return l


class Solution:

	def recamanSequence(self, n):
		ans = []
		ans.append(0)
		check = set()
		check.add(0)

		def rec(n, x):
			if n == x + 1:
				return
			if ans[n - 1] - n > 0 and ans[n - 1] - n not in check:
				check.add(ans[n - 1] - n)
				ans.append(ans[n - 1] - n)
			else:
				ans.append(ans[n - 1] + n)
				check.add(ans[n - 1] + n)
			rec(n + 1, x)
		rec(1, n)
		return ans


def sol(i, n, li):
	if i == n:
		return
	if li[i - 1] - i > 0 and li[i - 1] - i not in li:
		li[i] = li[i - 1] - i
	else:
		li[i] = li[i - 1] + i
	sol(i + 1, n, li)

class Solution:

	def recamanSequence(self, n):
		li = [0] * n
		sol(1, n, li)
		return li


class Solution:

	def recamanSequence(self, n):
		a = [0]
		count1 = 0
		if n == 1:
			return a
		a = [0] * n

		def rec(a, n, count1):
			if count1 >= n:
				return
			z = a[count1 - 1] - count1
			if z > 0 and z not in a:
				a[count1] = z
			else:
				x = a[count1 - 1] + count1
				a[count1] = x
			return rec(a, n, count1 + 1)
		rec(a, n, count1 + 1)
		return a


class Solution:

	def rec(self, n, res):
		if n == 0:
			res.append(0)
			return 0
		else:
			x = self.rec(n - 1, res)
			if x - n > 0:
				if x - n not in res:
					res.append(x - n)
					return x - n
				else:
					res.append(x + n)
					return x + n
			else:
				res.append(x + n)
				return x + n

	def recamanSequence(self, n):
		res = []
		self.rec(n, res)
		return res


from collections import defaultdict

class Solution:

	def recamanSequence(self, n):
		ans = []
		visited = defaultdict(bool)
		for i in range(n):
			if i == 0:
				ans.append(0)
				visited[0] = True
			else:
				temp = ans[-1] - i
				if temp < 0 or visited[temp]:
					newtemp = ans[-1] + i
					ans.append(newtemp)
					visited[newtemp] = True
				else:
					ans.append(temp)
					visited[temp] = True
		return ans


class Solution:

	def recamanSequence(self, n):

		def recaman(n, s, lis):
			if n == 0:
				lis.append(0)
				return 0
			val = recaman(n - 1, s, lis)
			if val - n > 0 and val - n not in s:
				s.add(val - n)
				lis.append(val - n)
			else:
				s.add(val + n)
				lis.append(val + n)
			return lis[-1]
		s = {0}
		lis = []
		recaman(n, s, lis)
		return lis
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		ans = ob.recamanSequence(n)
		for i in range(n):
			print(ans[i], end=' ')
		print()


class Solution:

	def recamanSequence(self, n):
		a = []
		if n == 0:
			a.append(0)
			return a
		else:
			b = self.recamanSequence(n - 1)
			a = a + b
			if a[n - 1] - n > 0 and a[n - 1] - n not in b:
				a.append(a[n - 1] - n)
			else:
				a.append(a[n - 1] + n)
			return a
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		ans = ob.recamanSequence(n)
		for i in range(n):
			print(ans[i], end=' ')
		print()


class Solution:

	def recamanSequence(self, n):
		if n <= 0:
			return
		s = set()
		s.add(0)
		arr = [0] * n
		for i in range(1, n):
			curr = arr[i - 1] - i
			if curr < 0 or curr in s:
				curr = arr[i - 1] + i
			s.add(curr)
			arr[i] = curr
		return arr


class Solution:

	def recamanSequence(self, n):
		a = [0] * (n + 1)
		for i in range(0, n + 1):
			x = a[i - 1] - i
			if x > 0 and x not in a:
				a[i] = x
			else:
				a[i] = x + 2 * i
		return a


class Solution:

	def result(self, n, d, sol):
		if n == 0:
			sol[0] = 0
			return 0
		prev_iter = self.result(n - 1, d, sol)
		val1 = prev_iter - n
		if val1 > 0 and val1 not in d:
			d[prev_iter - n] = 1
			sol[n] = prev_iter - n
			return prev_iter - n
		d[prev_iter + n] = 1
		sol[n] = prev_iter + n
		return prev_iter + n

	def recamanSequence(self, n):
		d = {}
		sol = {}
		self.result(n - 1, d, sol)
		return [sol[i] for i in range(n)]


class Solution:

	def recamanSequence(self, n):

		def rec(n, res):
			if n == 0:
				res.append(n)
				return
			rec(n - 1, res)
			temp = res[n - 1] - n
			if temp <= 0 or temp in res:
				temp = res[n - 1] + n
			res.append(temp)
			return
		res = []
		rec(n, res)
		return res


class Solution:

	def recursive(self, i, n, lst):
		if i == n:
			return lst
		if lst[i - 1] - i > 0 and lst[i - 1] - i not in lst:
			lst[i] = lst[i - 1] - i
		else:
			lst[i] = lst[i - 1] + i
		self.recursive(i + 1, n, lst)
		return lst

	def recamanSequence(self, n):
		lst = [0 for _ in range(n)]
		self.recursive(1, n, lst)
		return lst


class Solution:

	def recamanSequence_h(self, n, i, ans):
		if i == n:
			return ans
		if ans[i - 1] - i > 0 and ans[i - 1] - i not in ans:
			ans[i] = ans[i - 1] - i
		else:
			ans[i] = ans[i - 1] + i
		return self.recamanSequence_h(n, i + 1, ans)

	def recamanSequence(self, n):
		ans = [0] * n
		i = 1
		self.recamanSequence_h(n, i, ans)
		return ans


def sequence(n, arr):
	if n == 0:
		arr.append(0)
		return 0
	a = sequence(n - 1, arr)
	if a - n > 0 and a - n not in arr:
		arr.append(a - n)
	else:
		arr.append(a + n)
	return arr[-1]

class Solution:

	def recamanSequence(self, n):
		arr = []
		sequence(n, arr)
		return arr


class Solution:

	def recamanSequence(self, n):
		if n == 0:
			return
		a = [0] * n
		for i in range(1, n):
			temp = a[i - 1] - i
			if temp <= 0:
				temp = a[i - 1] + i
				a[i] = temp
				continue
			if temp in a:
				temp = a[i - 1] + i
			a[i] = temp
		return a


class Solution:

	def helper(self, n, i, ans):
		if i == n:
			return ans
		if ans[i - 1] - i > 0 and ans[i - 1] - i not in ans:
			ans[i] = ans[i - 1] - i
		else:
			ans[i] = ans[i - 1] + i
		return self.helper(n, i + 1, ans)

	def recamanSequence(self, n):
		ans = [0] * n
		output = self.helper(n, 0, ans)
		return ans


class Solution:

	def sol(self, n, l, N):
		if l[n - 1] - n > 0 and l[n - 1] - n not in l:
			l.append(l[n - 1] - n)
		else:
			l.append(l[n - 1] + n)
		if n == N:
			return l
		return self.sol(n + 1, l, N)

	def recamanSequence(self, n):
		l = [0]
		return self.sol(1, l, n)


class Solution:

	def recamanSequence(self, n):
		arr = []
		i = 1
		arr.append(0)
		self.solve(arr, n, i)
		return arr

	def solve(self, arr, n, i):
		if i == n:
			return
		if arr[i - 1] - i > 0 and arr[i - 1] - i not in arr:
			x = arr[i - 1] - i
			arr.append(x)
			i = i + 1
			self.solve(arr, n, i)
		else:
			x = arr[i - 1] + i
			arr.append(x)
			i = i + 1
			self.solve(arr, n, i)


class Solution:

	def recamanSequence(self, n):
		res = [0] * n
		if n > 0:
			for i in range(1, n):
				temp = res[i - 1] - i
				if temp > 0 and temp not in res:
					res[i] = temp
				else:
					temp = 0
					temp = res[i - 1] + i
					res[i] = temp
		return res


class Solution:

	def recamanSequence(self, n):
		a = []

		def solve(n, a, i):
			if i == 0:
				a.append(i)
			elif i == 1:
				a.append(i)
			elif a[i - 1] - i > 0 and a[i - 1] - i not in a:
				a.append(a[i - 1] - i)
			else:
				a.append(a[i - 1] + i)
			if i == n:
				return
			solve(n, a, i + 1)
		solve(n, a, 0)
		return a


from collections import defaultdict

class Solution:

	def recamanSequence(self, n):
		h = defaultdict(lambda : False)
		seq = [0] * n
		for i in range(1, n):
			x = seq[i - 1] - i
			if x > 0 and h[x] == False:
				seq[i] = x
			else:
				seq[i] = seq[i - 1] + i
			h[seq[i]] = True
		return seq


class Solution:

	def recamanSequence(self, n):
		arr = [0]
		aa = set()
		for i in range(1, n):
			if arr[-1] - i > 0 and arr[-1] - i not in aa:
				aa.add(arr[-1] - i)
				arr.append(arr[-1] - i)
			else:
				aa.add(arr[-1] + i)
				arr.append(arr[-1] + i)
		return arr


class Solution:

	def recamanSequence(self, n):
		li = [0] * n
		self.recman_sequence(n, li)
		return li

	def recman_sequence(self, n, li):
		for i in range(1, n):
			if li[i - 1] - i > 0 and li[i - 1] - i not in li:
				li[i] = li[i - 1] - i
			else:
				li[i] = li[i - 1] + i
		return li


class Solution:

	def recamanSequence(self, n):
		if n <= 0:
			return
		res = []
		res.append(0)
		sett = set()
		sett.add(0)
		if n == 1:
			return res
		pre = 0
		for i in range(1, n):
			curr = pre - i
			if curr < 0 or curr in sett:
				curr = pre + i
			sett.add(curr)
			res.append(curr)
			pre = curr
		return res


class Solution:

	def recamanSequence(self, n):
		res = [0]
		d = {}

		def func(n, i=1):
			if i == n:
				return
			ans = res[i - 1] - i
			if ans in d or ans <= 0:
				ans = res[i - 1] + i
			d[ans] = 1
			res.append(ans)
			func(n, i + 1)
		func(n)
		return res


from collections import defaultdict

class Solution:

	def recamanSequence(self, n):
		res = [0]
		d = defaultdict(int)
		for i in range(1, n):
			ans = res[i - 1] - i
			if ans in d or ans <= 0:
				ans = res[i - 1] + i
			d[ans] += 1
			res.append(ans)
		return res


class Solution:

	def recamanSequence(self, n):
		if n == 0:
			return [0]
		li = [0]
		for i in range(1, n):
			l = li[i - 1]
			z = l - i
			if z < 0 or z in li:
				z = l + i
			li.append(z)
		return li


class Solution:

	def seq(self, curr, n, List):
		if curr == n + 1:
			return List
		if curr == 0:
			List.append(curr)
			return self.seq(curr + 1, n, List)
		x = List[-1]
		if x - curr > 0 and x - curr not in List:
			List.append(x - curr)
		else:
			List.append(x + curr)
		return self.seq(curr + 1, n, List)

	def recamanSequence(self, n):
		List = []
		self.seq(0, n, List)
		return List


class Solution:

	def recamanSequence(self, n):
		d = {0: 0}
		res = [0]
		for i in range(1, n + 1):
			if res[-1] - i > 0 and res[-1] - i not in d:
				a1 = res[-1] - i
			else:
				a1 = res[-1] + i
			res.append(a1)
			d[a1] = 1
		return res