Given N doors and N persons. The doors are numbered from 1 to N and persons are given id’s numbered from 1 to N. Each door can have only two statuses i.e. open (1) or closed (0) . Initially all the doors have status closed. Find the final status of all the doors, when all the persons have changed the status of the doors of which they are authorized. i.e. if status open then change the status to closed and vice versa. A person with id ‘i’ is authorized to change the status of door numbered ‘j’ if ‘j’ is a multiple of ‘i’.
Note: A person has to change the current status of all the doors for which he is authorized exactly once.
 
Example 1: 
Input:
N = 3
Output:
1 0 0 
Explanation:
Initiall status of rooms - 0 0 0. 
Person with id 2 changes room 2 to open,
i.e. (0 1 0). Person with id 1 changes
room 1, 2, 3 status (1 0 1).
Person with id 3 changes room 3
status i.e. (1 0 0).
Example 2: 
Input:
N = 2
Output:
1 0
Explanation:
Initiall status of rooms - 0 0. 
Person with id 2 changes room 2 to open,
i.e. (0 1). Person with id 1 changes
room 1, 2 status (1 0).
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function checkDoorStatus() which takes an Integer N as input and returns an array as the answer.
 
Expected Time Complexity: O(N*sqrt(N))
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

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

Solutions:
class Solution:

	def checkDoorStatus(self, N):
		stats = [0] * N
		for i in range(1, N + 1):
			s = int(math.sqrt(i))
			if s * s == i:
				stats[i - 1] = 1
			else:
				stats[i - 1] = 0
		return stats


import math

class Solution:

	def checkDoorStatus(self, N):
		l = [0] * N
		for i in range(1, N + 1):
			ans = int(math.sqrt(i))
			if ans * ans == i:
				l[i - 1] = 1
			else:
				l[i - 1] = 0
		return l


class Solution:

	def checkDoorStatus(self, N):
		n = N
		arr = [0] * n
		for i in range(1, n + 1):
			k = i
			for j in range(1, n // i + 1):
				arr[k - 1] = 1 - arr[k - 1]
				k += i
		return arr


class Solution:

	def checkDoorStatus(self, N):
		doors = [0] * N
		for person in range(1, N + 1):
			for door in range(person, N + 1, person):
				doors[door - 1] ^= 1
		return doors


class Solution:

	def checkDoorStatus(self, N):
		arr = [1] * (N + 1)
		for i in range(2, len(arr)):
			j = i
			while j < len(arr):
				if arr[j] == 0:
					arr[j] = 1
				else:
					arr[j] = 0
				j = j + i
		return arr[1:]


class Solution:

	def checkDoorStatus(self, N):
		li = [0] * N
		for i in range(1, N + 1):
			a = int(math.sqrt(i))
			if a * a == i:
				li[i - 1] = 1
			else:
				li[i - 1] = 0
		return li


class Solution:

	def checkDoorStatus(self, N):
		ans = [1 for i in range(N)]
		for i in range(1, N):
			val = i + 1
			for j in range(i, N, val):
				if ans[j] == 0:
					ans[j] = 1
				else:
					ans[j] = 0
		return ans


class Solution:

	def checkDoorStatus(self, N):
		doors = [0] * N
		for i in range(1, N + 1):
			K = 1
			while i * K <= N:
				doors[i * K - 1] ^= 1
				K += 1
		return doors


class Solution:

	def checkDoorStatus(self, N):
		x = [0] * N
		i = 0
		n = 1
		while i < N:
			x[i] = 1
			i = i + (2 * n + 1)
			n += 1
		return x


class Solution:

	def checkDoorStatus(self, N):
		doors = [0] * N
		for i in range(1, N + 1):
			for j in range(i, N + 1, i):
				doors[j - 1] = 1 - doors[j - 1]
		return doors


class Solution:

	def checkDoorStatus(self, N):
		a = [0] * N
		for i in range(1, N + 1):
			v = int(i ** 0.5)
			if v * v == i:
				a[i - 1] = 1
			else:
				a[i - 1] = 0
		return a


class Solution:

	def checkDoorStatus(self, N):
		st = [0] * N
		for i in range(1, N + 1):
			p = int(i ** 0.5)
			if p * p == i:
				st[i - 1] = 1
			else:
				st[i - 1] = 0
		return st


class Solution:

	def checkDoorStatus(self, N):
		s = '1'
		p = 2
		while len(s) < N:
			for i in range(p):
				s += '0'
			s += '1'
			p += 2
		s = s[:N]
		return s


import math

class Solution:

	def checkDoorStatus(self, N):
		l = []
		for i in range(1, N + 1):
			sr = int(math.sqrt(i))
			if sr * sr == i:
				l.append(1)
			elif sr * sr != i:
				l.append(0)
		return l


class Solution:

	def checkDoorStatus(self, n):
		a = [0 for i in range(n)]
		for i in range(1, int(math.sqrt(n)) + 1):
			a[i * i - 1] = 1
		return a


from math import sqrt as s

class Solution:

	def checkDoorStatus(self, N):
		arr = [0] * 126787
		for i in range(1, N + 1):
			r = int(s(i))
			if r * r == i:
				arr[i - 1] = 1
			else:
				arr[i - 1] = 0
		arr = arr[0:N]
		return arr


class Solution:

	def checkDoorStatus(self, N):
		arr = [0] * N
		for id in range(1, N + 1):
			j = id
			while j < N + 1:
				if arr[j - 1] == 0:
					arr[j - 1] += 1
				else:
					arr[j - 1] -= 1
				j += id
		return arr


class Solution:

	def checkDoorStatus(self, N):
		res = [0] * N
		for i in range(1, N + 1):
			ans = math.sqrt(i)
			if ans == int(ans):
				res[i - 1] = 1
		return res


class Solution:

	def checkDoorStatus(self, N):
		status_list = [0 for _ in range(N)]
		for i in range(1, N + 1):
			temp = math.sqrt(i)
			if temp == int(temp):
				status_list[i - 1] = 1
		return status_list


class Solution:

	def checkDoorStatus(self, N):
		mylist = []
		for i in range(1, N + 1):
			j = int(math.sqrt(i))
			if i == j ** 2:
				mylist.append(1)
			else:
				mylist.append(0)
		return mylist


class Solution:

	def checkDoorStatus(self, N):
		d = []
		for i in range(1, N + 1):
			d.append(0)
		for i in range(1, N + 1):
			m = math.sqrt(i)
			if m == int(m):
				d[i - 1] = 1
		return d


from math import sqrt

class Solution:

	def checkDoorStatus(self, N):
		l = [1] * N
		for i in range(2, N + 1):
			for j in range(i, N + 1, i):
				if l[j - 1] == 0:
					l[j - 1] = 1
				else:
					l[j - 1] = 0
		return l


class Solution:

	def checkDoorStatus(self, N):
		d = {}
		for i in range(1, N + 1):
			d[i] = 1
		for i in range(2, N + 1):
			for j in range(i, N + 1, i):
				d[j] += 1
		x = [0] * N
		for i in range(1, N + 1):
			if d[i] % 2 == 0:
				x[i - 1] = 0
			else:
				x[i - 1] = 1
		return x


class Solution:

	def checkDoorStatus(self, N):
		self.N = N
		c = []
		for i in range(1, self.N + 1):
			num = int(math.sqrt(i))
			if num * num == i:
				c.append(1)
			else:
				c.append(0)
		return c


import math

class Solution:

	def checkDoorStatus(self, N):
		l = []
		for i in range(1, N + 1):
			if math.sqrt(i).is_integer():
				l.append(1)
			else:
				l.append(0)
		return l


class Solution:

	def checkDoorStatus(self, N):
		a = []
		for i in range(1, N + 1):
			if int(pow(i, 1 / 2)) * int(pow(i, 1 / 2)) == i:
				a.append(1)
			else:
				a.append(0)
		return a


class Solution:

	def checkDoorStatus(self, N):
		status = [0 for i in range(N)]
		for i in range(N):
			idx = i + 1
			curr = 1
			val = curr * idx
			while val <= N:
				if status[val - 1] == 1:
					status[val - 1] = 0
				else:
					status[val - 1] = 1
				curr += 1
				val = curr * idx
		return status


class Solution:

	def checkDoorStatus(self, N):
		l = [0] * N
		for i in range(1, N + 1):
			res = i * i
			if res <= N:
				l[res - 1] = 1
		return l


class Solution:

	def checkDoorStatus(self, N):
		ls = [0] * N
		for i in range(1, N + 1):
			s = int(math.sqrt(i))
			if s * s == i:
				ls[i - 1] = 1
			else:
				ls[i - 1] = 0
		ls = ls[0:N]
		return ls

	def checkDoorStatus2(self, N):
		ls = [0] * N
		for i in range(1, N + 1):
			for j in range(i - 1, N, i):
				ls[j] = int(not ls[j])
		return ls


class Solution:

	def checkDoorStatus(self, N):
		ls = [0] * N
		for i in range(1, N + 1):
			for j in range(i - 1, N, i):
				ls[j] = int(not ls[j])
		return ls


import math

def HasEvenFactors(n):
	theroot = math.sqrt(n)
	if math.floor(theroot) == theroot:
		return False
	return True

class Solution:

	def checkDoorStatus(self, N):
		statuses = []
		for i in range(1, N + 1):
			if HasEvenFactors(i):
				statuses.append(0)
			else:
				statuses.append(1)
		return statuses


class Solution:

	def checkDoorStatus(self, N):
		s = [0] * N
		for i in range(1, N + 1):
			sq = i * i
			if sq <= N:
				s[sq - 1] = 1
		return s


class Solution:

	def checkDoorStatus(self, N):
		self.door = [0] * N
		for number in range(1, N + 1):
			sq = number * number
			if sq <= N:
				self.door[sq - 1] = 1
		return self.door


class Solution:

	def checkDoorStatus(self, N):
		l = [0] * N
		for i in range(N, 1, -1):
			for j in range(1, N + 1):
				if j * i <= N:
					if l[j * i - 1] == 1:
						l[j * i - 1] = 0
					else:
						l[j * i - 1] = 1
				else:
					break
		for i in range(N):
			if l[i] == 0:
				l[i] = 1
			else:
				l[i] = 0
		return l


class Solution:

	def checkDoorStatus(self, N):
		lst = [0 for i in range(N)]
		j = 0
		while j <= N:
			for k in range(j, N, j + 1):
				if lst[k] == 1:
					lst[k] = 0
				else:
					lst[k] = 1
			j = j + 1
		return lst


class Solution:

	def checkDoorStatus(self, N):
		ans = [1] * (N + 1)
		cr = 1
		num = 1
		for i in range(2, len(ans) + 1):
			num = i
			while num < len(ans):
				if ans[num] == 0:
					ans[num] = 1
				else:
					ans[num] = 0
				num += i
		return ans[1:]


import math

class Solution:

	def checkDoorStatus(self, N):
		status = [0] * N
		for i in range(1, N + 1):
			sq = math.sqrt(i)
			if sq == int(sq):
				status[i - 1] = 1
		return status


class Solution:

	def checkDoorStatus(self, N):
		l = []
		for i in range(N):
			l.append(0)
		for i in range(1, N + 1):
			a = math.sqrt(i)
			if a == int(a):
				l[i - 1] = 1
		return l


class Solution:

	def checkDoorStatus(self, N):
		import math
		arr = [0] * N
		for i in range(1, N + 1):
			if math.ceil(math.sqrt(i)) == math.floor(math.sqrt(i)):
				arr[i - 1] = 1
		return arr


import math

class Solution:

	def checkDoorStatus(self, N):
		lst = [0] * N
		for itr in range(1, N + 1):
			if math.sqrt(itr).is_integer():
				lst[itr - 1] = 1
		return lst


import math

class Solution:

	def checkDoorStatus(self, N):
		l = []
		for i in range(N):
			l.append(0)
		for i in range(1, N + 1):
			a = math.sqrt(i)
			if a == int(a):
				l[i - 1] = 1
		return l
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)


class Solution:

	def checkDoorStatus(self, N):
		status = [0] * N
		for i in range(1, N + 1):
			sq = math.sqrt(i)
			if sq == int(sq):
				status[i - 1] = 1
		return status
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)


import math

class Solution:

	def checkDoorStatus(self, N):
		l1 = []
		for i in range(1, N + 1):
			if math.ceil(i ** 0.5) == math.floor(i ** 0.5):
				l1.append(1)
			else:
				l1.append(0)
		return l1
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)


class Solution:

	def checkDoorStatus(self, N):
		arr = []
		for i in range(1, N + 1):
			if i ** (1 / 2) - int(i ** (1 / 2)) == 0:
				arr.append(1)
			else:
				arr.append(0)
		return arr
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)


class Solution:

	def checkDoorStatus(self, N):
		arr = [0] * 10005
		for i in range(1, N + 1):
			s = int(math.sqrt(i))
			if s * s == i:
				arr[i - 1] = 1
			else:
				arr[i - 1] = 0
		arr = arr[0:N]
		return arr
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)


class Solution:

	def checkDoorStatus(self, N):

		def oddeve(n):
			import math
			count = 0
			k = math.sqrt(n)
			if k == math.floor(k):
				count += 1
			return count
		ans = []
		for i in range(1, N + 1):
			ans.append(oddeve(i))
		return ans
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)


class Solution:

	def checkDoorStatus(self, N):
		l = {}
		l1 = []
		x = 1
		for i in range(1, N + 1):
			if x * x == i:
				l[i] = 1
				x += 1
			else:
				l[i] = 0
		for i in range(1, N + 1):
			l1.append(l[i])
		return l1
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)


class Solution:

	def checkDoorStatus(self, n):
		l = [0] * n
		for i in range(n):
			if (i + 1) ** 0.5 % 1 == 0:
				l[i] = 1
		return l
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ptr = ob.checkDoorStatus(N)
		print(*ptr)