数字重组整除问题

数字重组整除问题

Description

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.

思路

就暴力解决（没有想到其他解法，如果有请在下方评论我），尝试所有的排列，找出其中最大的可以整除17的数。需要注意的是‘0’不能算作整除17。

python

import itertools
def solve(s):
    ans = -1
    if s == '0':
        return ans
    for ss in itertools.permutations(s):
        num = int(''.join(ss))
        if num % 17 == 0 and num > ans:
            ans = num
    return ans

C++也有求所有排列的库，Java应该没有，就要自己写一个回溯的算法去遍历所有的排列组合

Java

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < n; i++){
            String s = sc.nextLine();
            Arrays.asList(s.toCharArray());
            List<Character> remain = new ArrayList<>();
            for (Character ch: s.toCharArray()){
                remain.add(ch);
            }
            long res = solve("", remain);
            if (res == -1 || s.equals("0")) {
                System.out.println("Not Possible");
            }else{
                System.out.println(res);
            }
        }
    }

    public static long solve(String path, List<Character> remain){
        if (remain.size() == 0){
            return Long.parseLong(path) % 17 == 0 ? Long.parseLong(path):-1;
        }
        long ans = -1;
        for (Character ch: new ArrayList<>(remain)){
            remain.remove(ch);
            ans = Math.max(ans, solve(path+ch, remain));
            remain.add(ch);
        }
        return ans;
    }

}