Problem: Permutation divisibility

You are given a number. Your task is to check if there exists a permutation of the digits of this number which is divisible by 4.

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of one line. The line consists of a non negative integer N. This integer may have leading zeros.

Output:
Corresponding to each test case, in a new line, print 1 if such a permutation of this number exists or print 0 if such a permutation doesn’t exist.
Constraints:

1 ≤ T ≤ 100

0 ≤ N ≤ 10200              
Example:

Input

3
003
715
123456

Output

1
0
1

Explanation:
For 003, we have a permutation 300 which is divisible by 4.
For 123456, we have 123564 which is a permutation of 123456 and is divisible by 4.

In order to solve this problem, you must know that a number is divisible by 4 if it is 0, 4, 8 , or its last two digits divisible by 4.

Python 2.7:

from itertools import *
if __name__ == '__main__':
    dic = set()
    for _ in range(0, 96+1, 4):
        if _ < 10:
            dic.add('0'+str(_))
        else:
            dic.add(str(_))

    t = input()
    for _ in range(t):
        n = raw_input()
        #print n
        if int(n) == 0 or int(n) == 4 \
            or int(n) == 8:
            print 1
        else:
            for (a,b) in list(permutations(n, 2)):
                if  ''.join((a, b)) in dic \
                    or ''.join((b, a)) in dic:
                        print 1
                        break
            else:
                print 0

 

Advertisements