Given a number N check whether it is wierd or not. A number is weird if the sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of those divisors sums to the number itself.
 
Example 1:
Input: N = 70
Output: 1
Explanation: The smallest weird number 
is 70. Its proper divisors are 1, 2, 5, 
7, 10, 14, and 35; these sum to 74, but 
no subset of these sums to 70. 
Example 2:
Input: N = 12
Output: 0
Explanation: The number 12, for example,
is not weird, because the proper divisors 
of 12 are 1, 2, 3, 4, and 6, sum of 
divisors is 16; but there is a subset 
{2, 4, 6} with sum 12, i.e., 2+4+6 = 12.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function is_weird() which takes n as input parameter and returns 1 if the number is weird number otherwise returns 0.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 10000

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def is_weird(self, n):

		# Code here

Solutions:
class Solution:

	def is_weird(self, n):
		x = n
		s = 0
		for i in range(n - 1, 0, -1):
			if n % i == 0:
				s += i
				if i <= x:
					x -= i
		if x != 0 and s > n:
			return 1
		return 0


class Solution:

	def is_weird(self, n):
		l = []
		sum = 0
		s = 0
		for i in range(1, n // 2 + 1):
			if n % i == 0:
				l.append(i)
				sum += i
			else:
				continue
		l.sort(reverse=True)
		for j in range(len(l)):
			s += l[j]
			if s > n:
				s = s - l[j]
			elif s == n:
				break
			else:
				continue
		if sum >= n and s == n:
			return 0
		elif n == 1:
			return 0
		elif sum < n:
			return 0
		else:
			return 1


class Solution:

	def is_weird(self, n):
		x = n
		sum = 0
		ls = []
		i = n - 1
		while i >= 1:
			if n % i == 0:
				sum += i
				if i <= x:
					x -= i
			i -= 1
		if x != 0 and sum > n:
			return 1
		else:
			return 0


import math

class Solution:

	def is_weird(self, n):
		ans = [1]
		for i in range(2, n + 1):
			if i * i > n:
				break
			if n % i:
				continue
			if i == n // i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		ans.sort(reverse=True)
		if sum(ans) <= n:
			return 0
		for x in ans:
			if n >= x:
				n -= x
		if n == 0:
			return 0
		return 1


class Solution:

	def is_weired(self, n):
		l = [70, 836, 4030, 5830, 7192, 7912, 9272]
		s = len(l)
		for i in range(0, s):
			if l[i] == n:
				return 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_weired(n)
		print(ans)


class Solution:

	def is_weired(self, n):
		l = [70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792, 10990, 11410, 11690]
		if n in l:
			return 1
		else:
			return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_weired(n)
		print(ans)


class Solution:

	def is_weired(self, n):
		ans = [1]
		for i in range(2, n + 1):
			if i * i > n:
				break
			if n % i:
				continue
			if i == n // i:
				ans.append(i)
			else:
				ans.append(i)
				ans.append(n // i)
		ans.sort(reverse=True)
		if sum(ans) <= n:
			return 0
		for x in ans:
			if n >= x:
				n -= x
		if n == 0:
			return 0
		return 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.is_weired(n)
		print(ans)


class Solution:

	def is_weired(self, n):
		weird = [70, 836, 4030, 5830, 7192, 7912, 9272]
		for i in weird:
			if i == n:
				return 1
		return 0