Problem Description:
Given two integers N, d , find the smallest number that is a multiple
of d that could be formed by permuting the digits of N. You must use all the
digits of N, and if the smallest multiple of d has leading zeros, they can be
dropped. If no such number exists, output -1.
Input
A line containing two space separated integers, representing N and d.
Output
A single line giving the permutation of N that is the smallest multiple of d, without any leading zeroes, if any. If not such permutation exists, the output should be -1
Constraints
1≤N≤1000000000000
1≤d≤1000000
Example 1
Input
210
2
Output
2
Output
12
Example 2
Input
1707693158
853684
Output
513917768
853684
Output
513917768
Example 3
Input
531
2
Output
2
Output
-1
Explanation
Explanation
1. In first test case the minimum number formed using all the three digits
divisible by the given divisor is 012 which is equivalent to 12 and this is a
multiple of d = 2. Hence the output is 12.
2. In second test case the minimum number formed using all the digits divisible by the given divisor is 0513917768. So in this case the output will be 513917768.
3. In the last case all permutations of digits of N are odd and hence not divisible by d.
2. In second test case the minimum number formed using all the digits divisible by the given divisor is 0513917768. So in this case the output will be 513917768.
3. In the last case all permutations of digits of N are odd and hence not divisible by d.
This comment has been removed by the author.
ReplyDelete