Problem: Partition a number into two divisible parts

*Difficulty: Easy
Given a number (as string) and two integers a and b, divide the string in two non-empty parts such that the first part is divisible by a and second part is divisible by b. If string can not be divided into two non-empty parts, output “-1”, else print the two parts.

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 single line containing 3 space seperated number denoting the respective values of  n, a and b.
Output:

For each test case output a single line containing the two space seperated non-empty parts else print -1.
Constraints:

1<=T<=100

1<=N<=106

1<=a,b<=N
Example:

Input:

3
1200 4 3
123 12 3
125 12 5

Ouput:

12 00
12 3
-1

Approach:
With Python in my pocket, I don’t think this problem deserves a medium-hard rank. The constraints is not hard, 10^6 means the length of the longest input number is just 6. The only thing to keep in mind is alway think of exceptions. Exceptions here are two case, number with length 1 and 2.

Implementation: Python2.7

#code
def partitionToTwoPart(number, a, b):
    number = str(number)
    if len(number) < 2:
        return -1
    elif len(number) == 2:
        first, second = number[0], number[1]
        if int(first) % a == 0 and int(second) % b == 0:
            return first, second
        else:
            return -1
    else:
        for i in range(1, len(number)):
            first, second = number[:i], number[i:]
            if int(first) % a == 0 and int(second) % b == 0:
                return first, second
        else:
            return -1

def main():
    t = input()
    for _ in range(t):
        n, a, b = map(int, raw_input().strip().split())
        result = partitionToTwoPart(n, a, b)
        if result != -1:
            print result[0], result[1]
        else:
            print -1
if __name__ == '__main__':
    main()
Advertisements