首页 > 试题广场 >

数位重排

[编程题]数位重排
  • 热度指数:38 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
牛牛有一个正整数x,牛牛需要把数字x中的数位进行重排得到一个新数(不同于x的数),牛牛想知道这个新数是否可能是原x的倍数。请你来帮他解决这个问题。

输入描述:
输入包括t+1行,第一行包括一个整数t(1 ≤ t ≤ 10),
接下来t行,每行一个整数x(1 ≤ x ≤ 10^6)


输出描述:
对于每个x,如果可能重排之后变为自己的倍数输出"Possible", 否则输出"Impossible".
示例1

输入

2
14
1035

输出

Impossible
Possible
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static boolean reSorted(int num){

        //进行计数,0-9
        int[] array = new int[10];
        int m = num;
        while (m > 0){
            array[m % 10] ++;
            m = m / 10;
        }

        for (int i=2;i<10;i++){
            int n = num * i;
            int[] copy = Arrays.copyOf(array,10);
            if (same(copy,n)){
                return true;
            }
        }

        return false;
    }

    public static boolean same(int[] array,int n){
        while (n > 0){
            if (array[n % 10] <= 0)
                return false;
            array[n % 10] --;
            n = n / 10;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i=0;i<n;i++){
            int m = in.nextInt();
            if (reSorted(m)){
                System.out.println("Possible");
            }
            else {
                System.out.println("Impossible");
            }
        }
    }
}


1035
1035 * 2 = 2075 ,和1035不是同一组合
1035 * 3 = 3105 ,和1035是同一组合 返回true
发表于 2020-03-25 10:12:15 回复(0)

Python 调用排列组合包,不好意思,开挂了~

from itertools import permutations

def permut(string):
    """排列组合"""
    per_list = []
    for p in permutations(string):
        per_list.append(''.join(p))
    return per_list[1:]

t = int(input())
for _ in range(t):
    s = input()
    num = int(s)
    per = permut(s)
    flag = False
    for p in per:
        if p != s and int(p) % num == 0:
            flag = True
    if flag:
        print('Possible')
        flag = False
    else:
        print('Impossible')
发表于 2020-03-22 00:30:42 回复(0)