Given a number n, the task is to find out whether this number is a Smith Number or not. A Smith Number is a composite number whose sum of digits is equal to the sum of digits of its prime factorization.
 
Example 1:
Input:
n = 4
Output:
1
Explanation:
Prime factorization = 2, 2; and 2 + 2 = 4
Therefore, 4 is a Smith Number.
Example 2:
Input:
n = 6
Output:
0
Explanation:
Prime factorization = 2, 3; and 2 + 3 is
not 6. Therefore, 6 is Not a Smith Number.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function smithNum() which takes an Integer n as input and returns the answer.
 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
 
Constraints:
1 <= n <= 10^{5}

Difficulty: MEDIUM
Tags: Number theory

Mathematics
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3



class Solution:

    def smithNum(self, n):

        # code here 

Solutions:
class Solution:

	def smithNum(self, n):

		def f(n):
			if n == 0 or n == 1:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		if f(n):
			return 0
		temp = sum(map(int, str(n)))
		div = 2
		cnt = 0
		while n > 1:
			if n % div == 0:
				n //= div
				cnt += sum(map(int, str(div)))
			else:
				div += 1
		return 1 if cnt == temp else 0


import math

class Solution:

	def __init__(self):
		self.pl = self.primes()

	def primes(self):
		n = int(100000.0)
		pl = [True] * (n + 1)
		pl[0] = pl[1] = False
		lim = int(math.sqrt(n)) + 1
		for i in range(2, lim):
			for j in range(i * i, n + 1, i):
				if pl[i]:
					pl[j] = False
		res = []
		for i in range(2, n + 1):
			if pl[i]:
				res.append(i)
		return res

	def isPrime(self, n):
		if n == 1:
			return False
		else:
			lim = int(math.sqrt(n)) + 1
			for i in range(2, lim):
				if n % i == 0:
					return False
			return True

	def bsf(self, arr, k):
		n = len(arr)
		(l, h, idx) = (0, n - 1, -1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] > k:
				h = m - 1
			else:
				idx = m
				l = m + 1
		return arr[:idx + 1]

	def sod(self, n):
		ds = 0
		while n != 0:
			ds += n % 10
			n = n // 10
		return ds

	def smithNum(self, n):
		if self.isPrime(n):
			return 0
		else:
			sl = self.bsf(self.pl, n)
			(i, s, pfsd) = (0, 0, 0)
			dn = n
			while dn != 0 and i < len(sl):
				t = sl[i]
				if dn % t == 0:
					pfsd += self.sod(t)
					dn = dn // t
				else:
					i += 1
			if pfsd == self.sod(n):
				return 1
			return 0


class Solution:

	def smithNum(self, n):
		l1 = []
		sieve = [1] * (n + 1)
		for i in range(n + 1):
			sieve[i] = i
		sieve[1] = 0
		for i in range(2, int(n ** 0.5) + 1):
			if sieve[i] == i:
				for j in range(i * i, n + 1, i):
					if sieve[j] == j:
						sieve[j] = i
		if sieve[n] == n:
			return 0
		n1 = n
		n2 = n1
		add = 0
		while n != 1:
			m = sieve[n]
			if len(str(m)) != 1:
				while m != 0:
					add += m % 10
					m = m // 10
			else:
				add += m
			n = n // sieve[n]
		add_n = 0
		while n1 != 0:
			add_n += n1 % 10
			n1 = n1 // 10
		if add == add_n:
			return 1
		else:
			return 0


class Solution:

	def smithNum(self, n):
		b = ''
		l = []
		c = 2
		m = n
		while n > 1:
			if n % c == 0:
				b = b + str(c)
				l.append(c)
				n = n // c
			else:
				c += 1
		if len(l) == 1:
			return 0
		a = 0
		for i in b:
			a += int(i)
		s = 0
		while m > 0:
			s = s + m % 10
			m = m // 10
		if s == a:
			return 1
		return 0


class Solution:

	def smithNum(self, n):

		def isPrime(n, r=False):
			if n < 4:
				return n > 1
			(isDivisible, k, i) = (lambda n, i, r: n if n % i else i if r else r, int(n ** 0.5), 2)
			while i <= k:
				d = isDivisible(n, i, r)
				if d - n:
					return d
				i += i - 1 if i in (2, 3) else (i - 3) % 6
			return True

		def sod(m, s=0):
			while m > 0:
				s += m % 10
				m //= 10
			return s
		p = isPrime(n, True)
		(s, k, y) = (0, n, sod(n))
		while k > 1:
			pk = isPrime(k, True) if n - k else p
			i = k if pk == True else pk
			c = 0
			while k % i == 0:
				k //= i
				c += 1
			s += sod(i) * c
		return int(not (s - y or (p == 1 and n % 2)))


class Solution:

	def smithNum(self, n):

		def sod(m):
			s = 0
			while m > 0:
				s += m % 10
				m //= 10
			return s

		def isPrime(m):
			if not n % 2:
				return False
			k = int(m ** 0.5)
			for i in range(3, k + 1, 2):
				if not m % i:
					return False
			return True

		def nxtPrime(m):
			if m in (2, 3):
				return 2 * m - 1
			m += (m + 3) % 6
			while not isPrime(m):
				m += (m + 3) % 6
			return m
		(p, s, S) = (2, 0, sod(n))
		if n < 4:
			return 0
		if isPrime(n):
			return 0
		while n > 1:
			while not n % p:
				s += sod(p)
				n //= p
			p = nxtPrime(p)
		if S == s:
			return 1
		return 0


import math

def isprime(n):
	if n <= 1:
		return 0
	for i in range(2, n // 2 + 1):
		if n % i == 0:
			return 0
	return 1

class Solution:

	def smithNum(self, n):
		if isprime(n):
			return 0
		a = []
		k = n
		s = 0
		f = n
		x = 0
		while f:
			s += f % 10
			f //= 10
		while n % 2 == 0:
			a.append(2)
			n //= 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				temp = i
				while temp:
					a.append(temp % 10)
					temp //= 10
				n //= i
		if n > 2:
			while n:
				a.append(n % 10)
				n //= 10
		return 1 if s == sum(a) else 0


import math

class Solution:

	def smithNum(self, n):

		def primefact(n):
			l = []
			while n % 2 == 0:
				l.append(2)
				n = n // 2
			for i in range(3, math.ceil(math.sqrt(n)) + 1):
				while n % i == 0:
					l.append(i)
					n //= i
			if n > 2:
				l.append(n)
			return l

		def sumof(n):
			s = 0
			n = list(str(n))
			for i in n:
				s += int(i)
			return s
		a = []
		x = y = 0
		a = primefact(n)
		for i in a:
			y += sumof(i)
		x = sumof(n)
		if x == y and a[0] != n:
			return 1
		return 0


class Solution:

	def smithNum(self, n: int) -> int:
		if self.isPrime(n):
			return 0
		else:
			prime_factors = self.primeFactors(n)
			sum_factors = sum((self.sumDigits(x) for x in prime_factors))
			if sum_factors == self.sumDigits(n):
				return 1
			else:
				return 0

	@staticmethod
	def sumDigits(num: int) -> int:
		result = 0
		while num:
			result += num % 10
			num //= 10
		return result

	@staticmethod
	def primeFactors(num: int) -> list:
		result = []
		while num % 2 == 0:
			result.append(2)
			num //= 2
		for i in range(3, int(num ** 0.5) + 1, 2):
			while num % i == 0:
				result.append(i)
				num //= i
		if num > 1:
			result.append(num)
		return result

	@staticmethod
	def isPrime(num: int) -> bool:
		if num < 2:
			return False
		else:
			for i in range(2, int(num ** 0.5) + 1):
				if num % i == 0:
					return False
			return True


class Solution:

	def isPrime(self, n):
		if n <= 1:
			return False
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

	def sumdigits(self, x):
		return sum((int(i) for i in str(x)))

	def checkSmithNum(self, n):
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0 and self.isPrime(i):
				return self.sumdigits(i) + self.checkSmithNum(n // i)
		return self.sumdigits(n)

	def smithNum(self, n):
		if n == 1:
			return 0
		if self.isPrime(n):
			return 0
		sd = self.sumdigits(n)
		if sd == self.checkSmithNum(n):
			return 1
		return 0


class Solution:

	def smithNum(self, n):
		p = n
		k = int(n ** 0.5)
		s = 0
		g = 0
		l = []
		for i in str(n):
			s += int(i)
		for i in range(2, k + 1):
			while n % i == 0:
				l.append(i)
				n = n // i
		if n == p:
			return 0
		if n != 1:
			l.append(n)
		for i in l:
			for j in str(i):
				g += int(j)
		if g == s:
			return 1
		return 0


class Solution:

	def smithNum(self, n):
		r = 0
		b = n
		for i in range(2, n):
			while n % i == 0:
				d = i
				while d > 0:
					r += d % 10
					d = d // 10
				n = n // i
			if n == 0:
				break
		c = 0
		while b > 0:
			c += b % 10
			b = b // 10
		if r == c:
			return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.smithNum(n))


import math

class Solution:

	def primeFactors(self, n):
		l = []
		while n % 2 == 0:
			l.append(2)
			n = n // 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				l.append(i)
				n = n // i
		if n > 2:
			l.append(n)
		return l

	def find(self, x, n):
		c = 0
		while n % x == 0 and n != 0:
			c += 1
			n //= x
		return c

	def findsum(self, x):
		c = 0
		while x != 0:
			c += x % 10
			x //= 10
		return c

	def smithNum(self, n):
		d = {}
		l = self.primeFactors(n)
		if len(l) == 1:
			c = self.find(l[0], n)
			if c == 1:
				return 0
		for x in l:
			d[x] = self.find(x, n)
		s = 0
		r = self.findsum(n)
		for x in d:
			s += self.findsum(x) * d[x]
		if s == r:
			return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.smithNum(n))


import math

class Solution:

	def sum_of_digits(self, n):
		s = 0
		while n / 10 != 0:
			s += n % 10
			n = n // 10
		return s

	def factors_and_sum_of_digts(self, n):
		s = 0
		while n % 2 == 0:
			s += 2
			n = n / 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				n = n / i
				s += self.sum_of_digits(i)
		if s == 0:
			s += 1
		if n > 2:
			s += self.sum_of_digits(n)
		return s

	def smithNum(self, n):
		if n == 1:
			return 0
		s1 = int(self.factors_and_sum_of_digts(n))
		s = self.sum_of_digits(n)
		if s1 == s:
			return 1
		else:
			return 0


class Solution:

	def smithNum(self, n):
		a = prime(n)
		s = 0
		for i in range(len(a)):
			if a[i] > 9:
				temp = digit(a[i])
				s += temp
			else:
				s += a[i]
		x = digit(n)
		q = p(n)
		if q == 1:
			return 0
		elif s == x:
			return 1
		else:
			return 0

def digit(n):
	sum = 0
	for i in range(n):
		tem = n % 10
		sum += tem
		n = n // 10
	return sum

def prime(n):
	l = []
	c = 2
	while n > 1:
		if n % c == 0:
			l.append(c)
			n = n / c
		else:
			c = c + 1
	return l

def p(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(n / 2) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return 1
		else:
			return 0
	else:
		return 0


import math

class Solution:

	def sumofdigits(self, i):
		sum1 = 0
		while i > 0:
			sum1 += i % 10
			i = i // 10
		return sum1

	def smithNum(self, n):
		sumoffac = 0
		num = n
		numsum = ob.sumofdigits(n)
		count = 0
		while n % 2 == 0:
			count += 1
			sumoffac += 2
			n = n // 2
		for i in range(3, int(math.sqrt(n)) + 1, 2):
			while n % i == 0:
				count += 1
				sumoffac += ob.sumofdigits(i)
				n = n // i
		if n > 2:
			count += 1
			sumoffac += ob.sumofdigits(n)
		if numsum == sumoffac and count != 1:
			return 1
		else:
			return 0


class Solution:

	def smithNum(self, n):
		l = n
		a = 2
		c = []
		while n > 1:
			if n % a == 0:
				n = n // a
				c.append(a)
			else:
				a = a + 1
		s = 0
		for i in c:
			while i > 0:
				a = i % 10
				i = i // 10
				s = s + a
		g = 0
		while l > 0:
			a = l % 10
			l = l // 10
			g = g + a
		if len(c) == 1:
			return 0
		if s == g:
			return 1
		return 0


import math

class Solution:

	def prime(self, nhalf):
		listt = [2]
		num = 3
		while num <= nhalf:
			for p in listt:
				if num % p == 0:
					break
			else:
				listt.append(num)
			num += 2
		return listt

	def sod(self, num):
		total = 0
		while num > 0:
			r = num % 10
			total += r
			num = num // 10
		return total

	def smithNum(self, n):
		primes = self.prime(n // 2 + 1)
		summ = 0
		factors = []
		num = n
		for p in primes:
			while num % p == 0:
				factors.append(self.sod(p))
				num = num // p
		sum_n = self.sod(n)
		if sum_n == sum(factors):
			return 1
		else:
			return 0