Babul’s favourite number is 17. He likes the numbers which are divisible by 17. This time what he does is that he takes a number n and tries to find the largest number which is divisible by 17, by rearranging the digits. As the number increases he gets puzzled with his own task. So you as a programmer have to help him to accomplish his task.
Note: If the number is not divisible by rearranging the digits, then return “Not Possible”. n may have leading zeros.
Example 1:
Input: n = 17
Output: 17
Explanation: 17 is the largest number 
which is also divisible by 17. 
Example 2:
Input: n = 15
Output: 51
Explanation: 51 is the largest number
which is also divisible by 17.
Your Task:  
You dont need to read input or print anything. Complete the function largestDivisible() which takes n as input parameter and returns the largest number which is divisible by 17.
Expected Time Complexity: O(|n|*|n|!), where |n| denoting length of n.
Expected Auxiliary Space: O(1)
Constraints:
1<= n <=10^{10}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3
class Solution:
    def largestDivisible (self, n):
        # code here 

Solutions:
class Solution:

	def solve(self, k, n, d):
		if k == n - 1:
			num = 0
			for i in d:
				num = num * 10 + i
			if num % 17 == 0 and num > self.ans:
				self.ans = num
			return
		self.solve(k + 1, n, d)
		for i in range(k + 1, n):
			if d[i] != d[i - 1]:
				(d[i], d[k]) = (d[k], d[i])
				self.solve(k + 1, n, d)
				(d[i], d[k]) = (d[k], d[i])

	def largestDivisible(self, n):
		digits = [ord(c) - ord('0') for c in n]
		self.ans = -1
		sz = len(n)
		self.solve(0, sz, digits)
		if self.ans == -1:
			return 'Not Possible'
		return str(self.ans)


class Solution:

	def dfs(arr, lst, count, max_):
		if len(lst) == len(arr):
			ans = 0
			for j in range(len(lst)):
				ans += lst[j]
				ans *= 10
			ans //= 10
			if ans % 17 == 0:
				max_[0] = max(max_[0], ans)
			return
		for n in count:
			if count[n] > 0:
				count[n] -= 1
				lst.append(n)
				Solution.dfs(arr, lst, count, max_)
				count[n] += 1
				lst.pop()

	def largestDivisible(self, n):
		n = int(n)
		arr = []
		while n > 0:
			arr.append(n % 10)
			n = n // 10
		(lst, res) = ([], [])
		max_ = [0]
		count = {n: 0 for n in arr}
		for n in arr:
			count[n] += 1
		Solution.dfs(arr, lst, count, max_)
		if max_[0] == 0:
			return 'Not Possible'
		return max_[0]


class Solution:

	def dfs(arr, lst, count, max_):
		if len(lst) == len(arr):
			ans = 0
			for j in range(len(lst)):
				ans += lst[j]
				ans *= 10
			ans //= 10
			if ans % 17 == 0:
				max_[0] = max(max_[0], ans)
			return
		for n in count:
			if count[n] > 0:
				count[n] -= 1
				lst.append(n)
				Solution.dfs(arr, lst, count, max_)
				count[n] += 1
				lst.pop()

	def largestDivisible(self, n):
		n = int(n)
		arr = []
		while n > 0:
			arr.append(n % 10)
			n = n // 10
		(lst, res) = ([], [])
		max_ = [0]
		count = {n: 0 for n in arr}
		for n in arr:
			count[n] += 1
		Solution.dfs(arr, lst, count, max_)
		if max_[0] == 0:
			return 'Not Possible'
		return max_[0]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = input()
		ob = Solution()
		print(ob.largestDivisible(n))