数组变换

AI那点小事

发布于 2020-04-18 20:14:00

5820

发布于 2020-04-18 20:14:00

文章被收录于专栏：AI那点小事

牛牛有一个数组，里面的数可能不相等，现在他想把数组变为：所有的数都相等。问是否可行。牛牛可以进行的操作是：将数组中的任意一个数改为这个数的两倍。这个操作的使用次数不限，也可以不使用，并且可以对同一个位置使用多次。

输入描述: 输入一个正整数N (N <= 50) 接下来一行输入N个正整数，每个数均小于等于1e9.

输出描述: 假如经过若干次操作可以使得N个数都相等，那么输出”YES”, 否则输出”NO”

输入例子: 2 1 2

输出例子: YES

代码（90%，可能是Java用大数类超时了）：

/*
 * 对于每个数一直除2,直到数的最后一位为1。
 */

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] num = new int[N];
        for (int i = 0 ; i < N ; i++){
            num[i] = in.nextInt();
        }

        for( int i = 0 ; i < N ; i++){
            while((num[i] & 1) == 0){
                num[i] >>= 1;
            }
        }

        StringBuffer result = new StringBuffer("YES");
        for ( int i = 1 ; i < N ; i++){
            if ( num[i] != num[0]){
                int len = result.length();
                result.delete(0,len);
                result.append("NO");
            }
        }
        System.out.print(result);

        in.close();
    }

}