Problem: Largest Divisibility Test

*Difficulty: Medium

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 print “Not Possible”. N may have leading zeros.

Input:
The first line of input contains an integer T denoting the no of test cases. Each of the next T lines contains the number N.

Output:
For each test case in a new line print the desired output.

Constraints:
1<=T<=100
1<=N<=10^10

Example:
Input:

4
17
43
15
16

Output:
17
34
51
Not Possible

My approach: (it might be not an elegant, efficient solution, but it works).

Generate all permutations of number n, then check each permutation for 17-divisibility.
If there is no number divisible by 17, return None, otherwise, return max of those numbers.

I dont consider my solution is not cheating. I use Python since it has an enormous  amount of packages that support problem solving.
**’Life is short, why haven’t you learned Python yet?’ 🙂

Implementation: Python 2.7

import itertools

def largest_divisible_of(number):
    """
        generate all permutations of a number and 
        check each permutation if it is divisible by 17
        number: type string
        return: None if there is no number divisible by 17,
                otherwise, return max
    """
    divisibles = list(''.join(x) for x in itertools.permutations(list(number)) if int(''.join(x)) % 17 == 0)
    return None if len(divisibles) == 0 else max(divisibles)
    
if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = raw_input().strip()
        result = largest_divisible_of(n)
        print result if result is not None else 'Not Possible'

Solution took: 3.112 seconds (still < 5s)

Advertisements