Given a positive integer N, find the smallest number S such that the product of all the digits of S is equal to the number N. If there's no such number, Print "-1".
 
Example 1:
Input:
N = 100
Output:
455
Explanation:
4*5*5 = 100. There are no numbers
less than 455 with the product of
it's digit as 100.
Example 2:
Input:
N = 26
Output:
-1
Explanation:
There are no numbers which can form
a product of 26 with its digits.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function getSmallest() which takes an Integer N as input and returns the answer as a String.
 
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def getSmallest(self, N):

        # code here 

Solutions:
class Solution:

	def getSmallest(self, N):
		if N == 1:
			return 1
		r = []
		for i in range(9, 1, -1):
			while N % i == 0:
				N = N // i
				r.append(str(i))
		if N > 10:
			return -1
		return ''.join(r[::-1]) if r else -1


class Solution:

	def getSmallest(self, N):
		sr = ''
		for i in range(9, 1, -1):
			if N % i == 0:
				while N % i == 0:
					sr = str(i) + sr
					N = N // i
		if N == 1:
			if sr == '':
				sr = '1'
				return sr
			else:
				return sr
		else:
			return -1


class Solution:

	def getSmallest(self, n):
		if n == 1:
			return 1
		li = []
		for i in range(9, 1, -1):
			while n % i == 0:
				li.append(str(i))
				n //= i
		if n > 10:
			return -1
		return ''.join(li[::-1] if li else -1)


class Solution:

	def getSmallest(self, n):
		if n == 1:
			return 1
		else:
			(res, j) = (0, 0)
			for i in range(9, 1, -1):
				while n % i == 0:
					res = i * 10 ** j + res
					j += 1
					n = n // i
			if n != 1:
				return -1
			return res


class Solution:

	def getSmallest(self, N):

		def divisibleBy(num):
			flag = False
			for i in range(9, 1, -1):
				if num % i == 0:
					flag = True
					break
			if flag:
				return (i, num / i)
			else:
				return (-1, num)
		if N <= 9:
			return str(N)
		else:
			nums = []
			(div, quo) = divisibleBy(N)
			while quo > 1 and div != -1:
				nums.append(div)
				(div, quo) = divisibleBy(quo)
			if quo == 1:
				nums.append(div)
				nums.sort()
				nums = list(map(str, nums))
				return ''.join(nums)
			else:
				return '-1'


class Solution:

	def getSmallest(self, N):
		if N == 1:
			return 1
		cp = N
		res = []
		div = 9
		while N > 1 and div > 1:
			while N % div == 0:
				res.append(str(div))
				N //= div
			div -= 1
		if N > 1 and div == 1:
			return -1
		return int(''.join(reversed(res)))


import math

class Solution:

	def getSmallest(self, n):
		a = int(math.sqrt(n))
		i = 9
		l = []
		while i > 1 and n > 0:
			if n % i == 0:
				n = n // i
				l.append(i)
			else:
				i = i - 1
		if n > 1:
			return -1
		if len(l) == 0:
			return 1
		l.sort()
		ans = ''
		for i in l:
			ans += str(i)
		return ans


class Solution:

	def getSmallest(self, N):
		ans = ''
		if N == 1:
			return N
		for i in range(9, 1, -1):
			while N % i == 0:
				ans += str(i)
				N //= i
		if N > 10:
			return -1
		if ans:
			return ans[::-1]
		return -1


import numpy as np

class Solution:

	def getSmallest(self, N):
		if N < 10:
			return N
		num = N
		t = 9
		temp = []
		while num > 1 and t > 1:
			if num % t == 0:
				temp.append(t)
				num = num // t
			else:
				t -= 1
		if np.prod(temp) == N:
			return ''.join(map(str, temp[::-1]))
		else:
			return '-1'


class Solution:

	def getSmallest(self, N):
		k = int(N ** 0.5)
		l = []
		for i in range(2, 10):
			while N % i == 0:
				l.append(i)
				N = N // i
		if N >= 10:
			return -1
		if N != 1:
			l.append(N)
		l.sort()
		s = 1
		g = []
		for i in l:
			if s * i <= 9:
				s *= i
			else:
				g.append(s)
				s = i
		g.append(s)
		g.sort()
		t = ''
		for i in g:
			t += str(i)
		g = []
		s = 1
		for i in l[::-1]:
			if s * i <= 9:
				s *= i
			else:
				g.append(s)
				s = i
		g.append(s)
		g.sort()
		y = ''
		for i in g:
			y += str(i)
		return min(int(t), int(y))


class Solution:

	def getSmallest(self, n):
		if n == 1:
			return 1
		r = []
		for i in range(9, 1, -1):
			while n % i == 0:
				n = n // i
				r.append(str(i))
		if n > 10:
			return -1
		return ''.join(r[::-1]) if r else -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.getSmallest(N))


class Solution:

	def getSmallest(self, n):
		if n >= 1 and n <= 9:
			return n
		a = []
		for i in range(9, 1, -1):
			while n % i == 0:
				a.append(i)
				n = n // i
		if n != 1:
			return -1
		k = 0
		while len(a) != 0:
			k = k * 10 + a[-1]
			a.pop()
		return k
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.getSmallest(N))


class Solution:

	def getSmallest(self, N):
		if N <= 9:
			return N
		k = ''
		for i in range(9, 1, -1):
			while N % i == 0:
				N = N // i
				k += str(i)
		if N > 10:
			return -1
		return k[::-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.getSmallest(N))


class Solution:

	def getSmallest(self, N):
		if N == 1:
			return 1
		else:
			stack = []
			i = 9
			while i > 1:
				if N % i == 0:
					N = N // i
					stack.append(i)
					i += 1
				i -= 1
			if N == 1:
				stack.reverse()
				number = 0
				for i in stack:
					number = number * 10 + i
				return number
			else:
				return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.getSmallest(N))


class Solution:

	def getSmallest(self, N):
		if N in range(1, 10):
			return N
		if N <= 9:
			ans = 10 + N
			return ans
		temp = []
		for i in range(9, 1, -1):
			while N % i == 0:
				N = N / i
				temp.append(i)
		if N > 10:
			return '-1'
		N = temp[len(temp) - 1]
		for i in range(len(temp) - 2, -1, -1):
			N = N * 10 + temp[i]
		return N
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.getSmallest(N))


import numpy as np

class Solution:

	def getSmallest(self, N):
		if N < 10:
			return N
		num = N
		t = 9
		temp = []
		while num > 1 and t > 1:
			if num % t == 0:
				temp.append(t)
				num = num // t
			else:
				t -= 1
		if np.prod(temp) == N:
			return ''.join(map(str, temp[::-1]))
		else:
			return '-1'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.getSmallest(N))


class Solution:

	def getSmallest(self, N):
		if N <= 9:
			return N
		factors = []
		prev = -1
		while len(factors) != prev:
			prev = len(factors)
			for i in range(9, 1, -1):
				if N % i == 0:
					N = N / i
					factors.append(str(i))
					break
		if N != 1:
			return -1
		else:
			factors.sort()
			return ''.join(factors)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.getSmallest(N))


class Solution:

	def getSmallest(self, N):
		N = int(N)
		if N < 10:
			return N
		string = ''
		for div in range(9, 2 - 1, -1):
			while N % div == 0:
				string += str(div)
				N = N // div
		if N >= 10:
			return -1
		return string[::-1]


class Solution:

	def getSmallest(self, N):
		(i, prd) = (9, 1)
		temp = N
		if N == 1:
			return 1
		res = ''
		lst = []
		while i >= 2:
			while N % i == 0:
				N = N // i
				lst.append(i)
			i -= 1
		lst.sort()
		for j in lst:
			res += str(j)
			prd *= j
		if prd == temp:
			return res
		else:
			return '-1'


from collections import deque

class Solution:

	def getSmallest(self, N):
		if N < 9:
			return N
		res = ''
		i = 9
		while i >= 2:
			while N and N % i == 0:
				res = str(i) + res
				N = N // i
			i -= 1
		if N >= 10:
			return '-1'
		return int(res)


class Solution:

	def getSmallest(self, N):
		l = []
		t = N
		if N < 10:
			return N
		i = 9
		while i > 1 and t > 1:
			if t % i == 0:
				l.append(i)
				t = t // i
			else:
				i -= 1
		o = 1
		for v in l:
			o = o * v
		if o == N:
			return ''.join(map(str, l[::-1]))
		else:
			return -1


class Solution:

	def getSmallest(self, N):
		l = []
		if N <= 9:
			return N
		for i in range(9, 1, -1):
			while N % i == 0:
				N = N // i
				l.append(i)
		if N > 10:
			return -1
		return ''.join(map(str, l[::-1]))


import math
from functools import reduce

class Solution:

	def getSmallest(self, N):
		if N < 10:
			return N
		t = 9
		n = N
		num = N
		l = []
		while t > 1:
			if n % t == 0:
				l.append(t)
				n //= t
			else:
				t -= 1
		if len(l) > 0:
			result = reduce(lambda x, y: x * y, l)
			l.sort()
			if result == num:
				return ''.join(list(map(str, l)))
			else:
				return -1
		else:
			return -1


from collections import deque

class Solution:

	def getSmallest(self, N):
		if N < 10:
			return N
		i = 9
		ans = []
		while i > 1:
			while N % i == 0:
				N = N // i
				ans.append(i)
			i -= 1
		if N >= 10:
			return -1
		n = ans[-1]
		for i in range(len(ans) - 2, -1, -1):
			n = 10 * n + ans[i]
		return n


import numpy as np

class Solution:

	def getSmallest(self, N):
		if N <= 10:
			return N
		else:
			l = []
			n = N
			f = 9
			while n > 1 and f > 1:
				if n % f == 0:
					l.append(f)
					n = n / f
				else:
					f = f - 1
		if np.prod(l) == N:
			return ''.join(map(str, l[::-1]))
		else:
			return -1


import numpy as a

class Solution:

	def getSmallest(self, N):
		if N <= 10:
			return N
		first = 9
		que = N
		l = []
		while que > 1 and first > 1:
			if que % first == 0:
				l.append(first)
				que = que / first
			else:
				first = first - 1
		if a.prod(l) == N:
			return ''.join(map(str, l[::-1]))
		else:
			return -1


class Solution:

	def getSmallest(self, n):
		if n < 10:
			return n
		s = ''
		for i in range(9, 1, -1):
			while n > 1 and n % i == 0:
				s = str(i) + s
				n //= i
		if n > 1:
			return -1
		return s


class Solution:

	def getSmallest(self, N):
		if N == 1:
			return 1
		ans = ''
		for div in range(9, 1, -1):
			factor = 1
			while N % div == 0:
				if factor * div >= 10:
					ans = str(factor) + ans
					factor = 1
				else:
					N = N // div
					factor *= div
			if factor != 1:
				ans = str(factor) + ans
		if N != 1:
			return -1
		return int(ans)


class Solution:

	def getSmallest(self, N):
		if N < 10:
			return N
		res = []
		for i in range(9, 1, -1):
			while N % i == 0:
				N = N / i
				res.append(i)
		if N > 10:
			return -1
		N = res[len(res) - 1]
		for i in range(len(res) - 2, -1, -1):
			N = 10 * N + res[i]
		return N


class Solution:

	def getSmallest(self, N):
		arr = [0] * 4
		if N == 1:
			return 1
		j = 0
		for i in [2, 3, 5, 7]:
			while N % i == 0:
				arr[j] += 1
				N = N // i
			j += 1
		if N != 1:
			return -1
		narr = [0] * 10
		narr[8] = arr[0] // 3
		arr[0] %= 3
		if (arr[0] + arr[1]) % 2 == 1:
			if arr[0] == 0:
				narr[3] += 1
				arr[1] -= 1
			else:
				narr[2] = 1
				arr[0] -= 1
		if arr[0] == 1 and arr[1] % 2 == 1:
			narr[6] = 1
		narr[4] += arr[0] // 2
		narr[9] += arr[1] // 2
		narr[5] = arr[2]
		narr[7] = arr[3]
		s = ''
		for i in range(10):
			if narr[i] > 0:
				s = s + str(i) * narr[i]
		return s


class Solution:

	def getSmallest(self, N):
		if N == 1:
			return '1'
		c = []
		a = 2
		d = 0
		while N > 1:
			if N % a == 0:
				N = N // a
				d = d + 1
				if d > 1 and a <= 3:
					p = a ** d
					if p <= 9:
						c.remove(a ** (d - 1))
						c.append(p)
						continue
					if p > 10:
						d = 1
						c.append(a)
						continue
				if d > 1 and a > 3:
					c.append(a)
					continue
				else:
					c.append(a)
			else:
				a = a + 1
				d = 0
			if a > 9:
				return '-1'
		if 3 in c and 4 in c:
			c.remove(3)
			c.remove(4)
			c.append(2)
			c.append(6)
		if 3 in c and 2 in c:
			c.remove(2)
			c.remove(3)
			c.append(6)
		c.sort()
		return ''.join((str(x) for x in c))


class Solution:

	def getSmallest(self, N):
		if N < 10:
			return N
		ls = []
		for i in range(9, 1, -1):
			if N < 2:
				break
			while N % i == 0:
				ls.append(i)
				N = N // i
		if len(ls) == 0 or N > 10:
			return -1
		ls.reverse()
		ans = ''.join([str(i) for i in ls])
		return int(ans)


class Solution:

	def getSmallest(self, N):
		if N == 1:
			return 1
		nums = [0 for i in range(10)]
		i = 9
		while N and i > 1:
			if N % i == 0:
				nums[i] += 1
				N //= i
			else:
				i -= 1
		if N > 9:
			return -1
		ans = 0
		for i in range(10):
			if nums[i] != 0:
				while nums[i] != 0:
					ans = ans * 10 + i
					nums[i] -= 1
		return ans


class Solution:

	def getSmallest(self, N):
		a = []
		if N < 10:
			return str(N)
		for x in range(9, 1, -1):
			while N % x == 0:
				a.append(x)
				N //= x
		if N > 9:
			return -1
		if N > 1:
			a.append(N)
		return ''.join(map(str, sorted(a)))


class Solution:

	def getSmallest(self, N):
		t = 0
		if 1 <= N <= 9:
			return N
		for i in range(9, 1, -1):
			while N % i == 0:
				t = t * 10 + i
				N = N // i
			if N == 1:
				break
		if N > 1:
			return -1
		s = 0
		while t > 0:
			r = t % 10
			s = s * 10 + r
			t = t // 10
		return s


import math

class Solution:

	def getSmallest(self, n):
		if n >= 0 and n <= 9:
			return n
		digits = list()
		for i in range(9, 1, -1):
			while n % i == 0:
				digits.append(i)
				n = n // i
		if n != 1:
			return -1
		k = 0
		while len(digits) != 0:
			k = k * 10 + digits[-1]
			digits.pop()
		return k


class Solution:

	def getSmallest(self, n):
		ans = []
		if n < 10:
			return n
		else:
			for i in range(9, 1, -1):
				while n % i == 0:
					n = n / i
					ans.append(i)
		if n > 10:
			return -1
		s = ''
		for i in range(len(ans) - 1, -1, -1):
			s += str(ans[i])
		return int(s)


import numpy as np

class Solution:

	def getSmallest(self, N):
		if N <= 10:
			return N
		else:
			list1 = []
			number = N
			first = 9
			while number > 1 and first > 1:
				if number % first == 0:
					list1.append(first)
					number /= first
				else:
					first -= 1
			if np.prod(list1) == N:
				return ''.join(map(str, list1[::-1]))
			else:
				return '-1'


class Solution:

	def getSmallest(self, N):
		if N < 10 and N > 1:
			return N
		l = []
		s = ''
		if N == 1:
			return N
		while N:
			if N % 9 == 0:
				l.append(9)
				N = N // 9
			elif N % 8 == 0:
				l.append(8)
				N = N // 8
			elif N % 7 == 0:
				l.append(7)
				N = N // 7
			elif N % 6 == 0:
				l.append(6)
				N = N // 6
			elif N % 5 == 0:
				l.append(5)
				N = N // 5
			elif N % 4 == 0:
				l.append(4)
				N = N // 4
			elif N % 3 == 0:
				l.append(3)
				N = N // 3
			elif N % 2 == 0:
				l.append(2)
				N = N // 2
			else:
				break
		for i in l:
			s += str(i)
		s = s[::-1]
		if N == 1:
			return s
		else:
			return -1


class Solution:

	def getSmallest(self, N):
		N = int(N)
		l = 0
		if N == 1:
			return '1'
		while N > 1:
			if N % 9 == 0:
				N = N // 9
				l = l * 10 + 9
			elif N % 8 == 0:
				N = N // 8
				l = l * 10 + 8
			elif N % 7 == 0:
				N = N // 7
				l = l * 10 + 7
			elif N % 6 == 0:
				N = N // 6
				l = l * 10 + 6
			elif N % 5 == 0:
				N = N // 5
				l = l * 10 + 5
			elif N % 4 == 0:
				N = N // 4
				l = l * 10 + 4
			elif N % 3 == 0:
				N = N // 3
				l = l * 10 + 3
			elif N % 2 == 0:
				N = N // 2
				l = l * 10 + 2
			else:
				return '-1'
				break
		s = str(l)
		return s[::-1]


class Solution:

	def getSmallest(self, N):
		n = 9
		st = ''
		if N == 1:
			return '1'
		while n != 1:
			if N % n == 0:
				st = str(n) + st
				N = N / n
				n = 10
			n -= 1
		if N == 1:
			return st
		else:
			return -1


class Solution:

	def getSmallest(self, N):
		ans = ''
		if N != 1:
			while N > 1:
				if N % 9 == 0:
					N = N // 9
					ans = ans + '9'
				elif N % 8 == 0:
					N = N // 8
					ans = ans + '8'
				elif N % 7 == 0:
					N = N // 7
					ans = ans + '7'
				elif N % 6 == 0:
					N = N // 6
					ans = ans + '6'
				elif N % 5 == 0:
					N = N // 5
					ans = ans + '5'
				elif N % 4 == 0:
					N = N // 4
					ans = ans + '4'
				elif N % 3 == 0:
					N = N // 3
					ans = ans + '3'
				elif N % 2 == 0:
					N = N // 2
					ans = ans + '2'
				else:
					return -1
		else:
			return 1
		ans = ans[::-1]
		ans = int(ans)
		return ans