Given an integer N, list all the divisors of N (excluding N) in sorted order. Find the number formed by performing the XOR operation on each divisor in the list.
Example 1:
Input: N = 10
Output:
1 2 5
6
Explanation:
All the proper divisors are 1, 2 and 5.
1 XOR 2 XOR 5 = 6
Example 2:
Input: N = 8
Output:
1 2 4
7
Explanation:
All the proper divisors are 1, 2 and 4.
1 XOR 2 XOR 4 = 7
Your Task:
You don't need to read or print anything. Your task is to complete the function xor_play() which takes N as input parameter and returns a list of integers containing all the proper divisors in sorted order. The last element in the list must contain the XOR result.
Expected Time Complexity: O(sqrt(N))
Expected Space Complexity: O(K) where K is the number of divisors of N.
 
Constraints:
1 <= N <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics

Starter code: #User function Template for python3



class Solution:

	def xor_play(self, n):

		# code here



Solutions:
class Solution:

	def xor_play(self, n):
		if n == 1:
			return [0]
		result = [1]
		i = 2
		while i * i <= n:
			if n % i == 0:
				result.append(i)
				if i != n // i:
					result.append(n // i)
			i += 1
		result.sort()
		xor_result = 0
		for d in result:
			xor_result ^= d
		result.append(xor_result)
		return result


class Solution:

	def xor_play(self, n):
		if n == 1:
			return [0]
		res1 = []
		res2 = []
		xor = 0
		for i in range(1, int(n ** (1 / 2)) + 1):
			if n % i == 0:
				res1.append(i)
				xor ^= i
				if n // i != i and n // i != n:
					res2.append(n // i)
					xor ^= n // i
		res2 = res2[::-1]
		res1 = res1 + res2
		res1.append(xor)
		return res1


import math

class Solution:

	def xor_play(self, n):
		s = list()
		ans = 1
		if n == 1:
			s.append(0)
			return s
		s.append(ans)
		size = int(math.sqrt(n)) + 1
		for i in range(2, size):
			if n % i == 0:
				if i == n // i:
					s.append(i)
					ans ^= i
				else:
					s.append(i)
					s.append(n // i)
					ans ^= i
					ans ^= n // i
		s.sort()
		s.append(ans)
		return s


import math
from functools import reduce

class Solution:

	def xor_play(self, n):
		l = []
		if n == 1:
			return [0]
		for i in range(1, int(math.sqrt(n)) + 1):
			if n % i == 0:
				if n / i == i:
					l.append(i)
				else:
					l.extend([i, n // i])
		if n in l:
			l.remove(n)
		l.sort()
		xor = reduce(lambda a, b: a ^ b, l)
		l.append(xor)
		return l


import math
from functools import reduce

class Solution:

	def xor_play(self, n):
		l = []
		if n == 1:
			return [0]
		xor = 0
		for i in range(1, int(math.sqrt(n)) + 1):
			if i == 1:
				l.append(i)
				xor ^= 1
				continue
			if n % i == 0:
				if n / i == i:
					l.append(i)
					xor ^= i
				else:
					l.extend([i, n // i])
					xor = xor ^ i ^ n // i
		l.sort()
		l.append(xor)
		return l


import math

class Solution:

	def xor_play(self, n):
		if n == 1:
			return [0]
		final = [1]
		ans = 1
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				ans ^= i
				final.append(i)
				if i != n // i:
					ans ^= n // i
					final.append(n // i)
		final = sorted(final)
		final.append(ans)
		return final


class Solution:

	def xor_play(self, n):
		if n == 1:
			return [0]
		k = int(n ** 0.5)
		s = {1: 1}
		for i in range(2, k + 1):
			if n % i == 0:
				s[i] = 1
				s[n // i] = 1
		f = 0
		l = []
		for i in s:
			l.append(i)
			f = f ^ i
		l.sort()
		l.append(f)
		return l
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.xor_play(n)
		for i in range(len(ans) - 1):
			print(ans[i], end=' ')
		print()
		print(ans[-1])


import math

class Solution:

	def xor_play(self, n):
		if n == 1:
			return [0]
		siz = int(math.sqrt(n)) + 1
		result = []
		xor = 0
		for i in range(1, siz):
			if n % i == 0:
				if i == 1:
					xor = xor ^ i
					result.append(i)
				else:
					div = int(n / i)
					xor = xor ^ i
					result.append(i)
					if i != div:
						xor = xor ^ div
						result.append(div)
		result.sort()
		result.append(xor)
		return result


import math

class Solution:

	def xor_play(self, n):
		if n == 1:
			return [0]
		arr = [1]
		iterations = int(math.sqrt(n)) + 1
		for i in range(2, iterations):
			if n % i == 0:
				arr.append(i)
				if int(n / i) != i:
					arr.append(int(n / i))
		arr.sort()
		xor = 0
		for i in arr:
			xor ^= i
		arr.append(xor)
		return arr