首页 > 试题广场 > 数组变换
[编程题]数组变换
  • 热度指数:3602 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
牛牛有一个数组,里面的数可能不相等,现在他想把数组变为:所有的数都相等。问是否可行。
牛牛可以进行的操作是:将数组中的任意一个数改为这个数的两倍。
这个操作的使用次数不限,也可以不使用,并且可以对同一个位置使用多次。

数据范围:数组大小满足 ,数组中的数满足

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


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

输入

2
1 2

输出

YES
示例2

输入

3
1 2 3

输出

NO
此题知识点应该是考如何判断一个整数是2的指数幂

满足YES条件,可知所有数因式分解后,只有2的个数不同.
因此一个for循环,两个两个处理,用大数除以小数,得到商和余数.
如果商不是2的幂,或者余数不等于0,则终止循环,输出NO。

证明商是否2的指数幂,可以使用二进制规律,2的指数幂对应的二进制中1的个数为1.
因此可以通过 n & (n-1) == 0 判断商是否2的指数幂。如8&7==0, 16&15=0

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = scanner.nextInt();
        }
        for(int i=1;i<n;i++){
            int small, big;
            if(a[i]>a[i-1]){
            	small = a[i-1];
               	big = a[i];
            }else{
            	small = a[i];
            	big = a[i-1];
            }
            int remainder = big % small;
            int quotient = big / small;
            if(remainder!=0||(quotient&(quotient-1))!=0)
            {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}

编辑于 2017-06-07 00:24:11 回复(0)
#include<stdio.h>
int a[50],i,n,flag=1;
int main(){
    for(scanf("%d",&n),i=0;i<n;i++){
        scanf("%d",a+i);
        while(a[i]%2==0) a[i]/=2;
        if(i>0&&a[i]!=a[i-1]) flag=0;
    }
    printf("%s\n",flag?"YES":"NO");
}

发表于 2017-11-11 12:53:07 回复(0)
把数组每一个元素都除以2,直到它为奇数。如果此时数组每个元素都一样,满足条件
import java.util.Scanner;
 
//校招模拟:数组变换
publicclassMain {
 
    publicstaticvoidmain(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = newScanner(System.in);
        intn = scanner.nextInt();
        int[] data = newint[n];
        for(inti = 0; i < n; i++) {
            data[i]=scanner.nextInt();
            while(data[i]%2==0) {
                data[i]=data[i]/2;         
            }
        }
        intflag = data[0];
        for(inti = 1; i < n; i++) {
            if(data[i]!=flag) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
        scanner.close();
    }
 
}

发表于 2017-05-20 00:42:31 回复(10)
#include<iostream>
#include<cstring>
using namespace std;
int main(){
    int n;
    int a[51];
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        while(a[i] % 2 == 0)    a[i] /= 2;
    }  
    for(int i = 1; i < n; i++){
        if(a[i] != a[i-1]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}
发表于 2017-05-24 17:25:45 回复(0)
#include <iostream>
using namespace std;

bool judge(int a, int b) {
    if (a != b) {   //不相等且除不尽,首先排除
        int mod = a > b ? a % b : b % a;
        if (mod) {
            return false;
        }
    }
    if (a == b) {
        return true;
    }
    int n = a > b ? a / b : b / a;
    while (n > 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            return false;
        }
    }
    return true;
}

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    string ok = "YES";
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!judge(arr[i], arr[j])) {
                ok = "NO";
                break;
            }
        }
        if (ok == "NO") {
            break;
        }
    }
    cout << ok;
    return 0;
}
发表于 2017-10-20 04:44:17 回复(0)
#include<iostream>
using namespace std;

char* isEqual(int arr[], int N)
{
for (int i = 0; i < N; i++)
{
while (arr[i] % 2 == 0)
arr[i] /= 2;
}
for (int i = 1; i < N; i++)
{
if (arr[i] != arr[0])
return "NO";
}
return "YES";
}

int main()
{
int n;
cin >> n;
int numb[81];
for (int i = 0; i < n; i++)
cin >> numb[i];
cout << isEqual(numb, n) << endl;
return 0;
}
发表于 2017-06-22 16:52:34 回复(0)
  1. 看着上面的回答改的,找出最大数,除各个数,能除尽并且结果全部是2的n次方的,就是满足条件的

    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main()
    {
    	vector<int> array;
    	int in, a;
    	cin >> in;
    	int count = 0;
    	for (int i = 0; i < in; i++)
    	{
    		cin >> a;
    		array.push_back(a);
    		//if (0== (a&(a - 1)))
    		//	count++;
    
    
    	}
    	std::vector<int>::iterator biggest = std::max_element(std::begin(array), std::end(array));
    	for (auto s:array)
    	{
    		if (*biggest%s == 0)
    		{
    			int temp = *biggest / s;
    			if (0 == (temp&(temp - 1)))
    				count++;
    
    		}
    	}
    	if (count == in)
    		cout << "YES" << endl;
    	else
    
    		cout << "NO" << endl;
    }
发表于 2017-06-05 11:25:42 回复(0)
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
bool iseq(int a[],int len){
    sort(a,a+len);
    bool flag=true;
    for(int k=1;k<len;k++){
        if(a[k]%a[k-1]!=0){
            flag=false;
            break;
        }
    }
    if(flag) return true;
    return false;
}
int main(){
    int n;
    cin>>n;
    int a[50];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(iseq(a,n)) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}
发表于 2017-07-29 12:01:15 回复(0)
追求极致,不盲目参考别人代码,容易限制自己思维,精简ac代码,喜欢请关注谢谢大家。
#include<iostream>
#include<algorithm>
using namespace std;
int ant[55];
int main(){
    int n;
    cin >> n;
    for(int i =0;i<n;i++){
        cin >> ant[i];
    }
    sort(ant,ant+n);
    int flag = 1;
    for(int i = 1;i<n;i++){
        if(ant[i]==ant[0])
            continue;
        if(ant[i]%ant[0]!=0){ 
                flag = 0;
        break;
        }
        if(ant[i]/ant[0]%2!=0)
            flag = 0;
    }
    if(flag){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

发表于 2017-05-23 21:16:31 回复(0)
我这样是不是慢了
import java.util.*;
 
public class Main {
 
 
    public static void main(String[] args) {
        boolean flag=true;
        Scanner scanner=new Scanner(System.in);
        int base = Integer.parseInt(scanner.nextLine());
        String s = scanner.nextLine();
        String[] s1 = s.split(" ");
        if(!("".equals(s))){
            List<Integer> tem=new ArrayList<>();
            for (String s2 : s1) {
                int anInt = Integer.parseInt(s2);
                tem.add(anInt);
            }
            //获取得数组中最小数的最小质数
            int min = getMinData(Collections.min(tem));
            for (String str : s1) {
                int i = Integer.parseInt(str);
                //排除自身
                if(min==i) continue;
                //如果有一个最小质数不相等则改变falg为false
                if((getMinData(i))!=min){
                    flag=false;
                }
            }
        }
        System.out.println(flag?"YES":"NO");
    }
    //递归获取每个数的最小质数
    public static  int getMinData(Integer  para){
        if(!((para/2)==0)&& ((para%2)==0)){
           return getMinData(para/2);
        }
        return para;
    }
}


发表于 2022-02-17 16:31:42 回复(0)
这题目是啥意思,完全没看懂
一个数组,里面的数可能不相等,现在他想把数组变为:所有的数都相等。问是否可行。
大佬们提交代码的时候,能不能帮忙解答一下题目的意思,感谢感谢
看了上面评论的,和这个题目好像没啥关系
发表于 2021-11-15 10:27:43 回复(1)
import java.util.Scanner;
public class Main{
    public static int remainder(int x){
        while(x % 2 == 0){
            x = x / 2;
        }
        return x;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] x = new int[N];
        for(int i = 0;i < N;i++){
            x[i] = in.nextInt();
        }
        for(int i = 1;i < N;i++){
            if(remainder(x[i]) != remainder(x[i - 1])){
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}
发表于 2021-10-14 19:44:31 回复(0)
#include <stdio.h>
#include <stdlib.h>

int array_len = 0;
int *array_adr = NULL;
int max_num = 0;
int temp = 0;

int main(void)
{
    scanf("%d\r\n",&array_len);
    array_adr = (int *)malloc(array_len*sizeof(int));
    if(array_adr == NULL){
        
        return -1;
    }else
        
    
    for(int i = 0;i < array_len; i++){
        scanf("%d\r\n",&array_adr[i]);
    }
    max_num = array_adr[array_len-1];
    for(int i = 0; i < array_len-1; i ++){
        temp = array_adr[i];
        while(temp != max_num){
            temp = 2*temp;
            if(temp > max_num){
                printf("NO\r\n");
                exit(0);
            }
        }
    }
    printf("YES\r\n");
    return 0;
}

发表于 2021-08-16 14:42:55 回复(0)
C语言解法:遍历数组,每个元素循环除以2直至奇数。再次遍历,若数组全部最简奇数一致则 YES
否则 NO
由于若采用乘法,将数组每个元素乘以2 的幂次倍数再载判断相等,没有明确的循环结束条件,可能存在循环过大,堆栈溢出问题,故逆向思维,将每个元素循环除以2,直至最简奇数,再判断是否一致。
(代码有点乱,未修改算法)
#include<stdio.h>
int fact(int n)
{
    int t;
    t=n;
    if(t%2==0)
    {
        while(t%2==0)
        {
            t/=2;
        }
        return t;
    }
    else return t;
}
int main()
{
    int n;
    while (scanf("%d",&n)!=EOF)
    {
        int i,t=0;
        int a[1000]={0};
        for(i=0;i<n;i++) scanf("%d",&a[i]);
        for(i=0;i<n-1;i++)
        {
            if(fact(a[i])!=fact(a[i+1]))
            {
                printf("NO\n");
                t=1;
                break;
            }
        }
        if(t!=1) printf("YES\n");
    }
    return 0;
}


发表于 2021-08-13 12:06:21 回复(0)
#include<iostream>
#include<vector>
using namespace std;
bool isEqual(vector<int> & res)
{
    int n=res.size();
    if(n==1)//只有一个元素
        return true;
    int i=0;
    for(; i<n-1; i++)
        if(res[i]!=res[i+1])
            break;
    if(i==2)//所有元素相等
        return true;
    int max=res[i],m=0;
    for(i=0; i<n; i++)
        if(res[i]>max)
        {
            max=res[i];
            m=i;
        }
    if(!max%2)//最大值是奇数
        return false;
    for(i=0; i<n; i++)
    {
        if(i==m)
            continue;
        if(res[i]==0)    //元素为0,且元素并不都相等
            return false;
        if(max%res[i]!=0)
            return false;
        int tmp=max/res[i];
        while(tmp!=1)
        {
            if(tmp%2==0)
                tmp/=2;
            else
                return false;
        }
    }
    return true;
}
int main()
{
    int N;
    cin>>N;
    vector<int> v;
    int a;
    while(N--)
    {
        cin>>a;
        v.push_back(a);
    }
    if(isEqual(v))
        cout<<"YES";
    else
        cout<<"NO";
    cout<<endl;
    return 0;
}

发表于 2021-08-11 22:45:07 回复(0)
先排个序再遍历  后者不等于前者并且后者除以前者的商不是2的倍数就报NO

N = int(input())
a = list(map(int,input().split()))

b = sorted(a)
flag = True
for i in range(N):
    for j in b[0:i]:
        if (b[i]!=j) and (b[i]/j)%2 != 0 :
            print('NO')
            flag = False
            break
        
    if flag == False:         
        break

if flag == True:
    print('YES')  
编辑于 2021-07-13 11:20:46 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
/*
* 牛牛有一个数组,里面的数可能不相等,现在他想把数组变为:所有的数都相等。问是否可行。
牛牛可以进行的操作是:将数组中的任意一个数改为这个数的两倍。
这个操作的使用次数不限,也可以不使用,并且可以对同一个位置使用多次。
*
* */
public class SameNumList {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        int size=Integer.parseInt(bufferedReader.readLine());
        String[] nums=bufferedReader.readLine().split(" ");
        int[] array=new int[size];
        for(int i=0;i<size;i++){
            array[i]=Integer.parseInt(nums[i]);
        }
        Arrays.sort(array);
        int max=array[size-1];
        boolean result=false;
        for(int i=0;i<array.length-1;i++){
            while(array[i]<max){
                array[i]*=2;
                if(array[i]==max){
                    break;
                }
            }
            if(array[i]==max){
                result=true;
            }else{
                result=false;
                break;
            }
        }
        if(result==true){
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }


    }
}

发表于 2020-08-17 11:16:25 回复(0)
python版本,思路是把数组每一个元素都除以2,直到它为奇数。如果此时数组每个元素都一样,满足条件,一楼的思想
def test():
    length = int(input())
    # list_1 = [int(i) for i in input().split()]
    list_1 = list(map(int,input().split()))
    for i in range(length):
        while list_1[i]%2==0:
            list_1[i] /= 2
        else:
            continue
    list_1 = set(list_1)
    if len(list_1)==1:
        print("YES")
    else:
        print("NO")


发表于 2019-08-27 09:47:04 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
         if(n<2){
            System.out.println("YES");
             return;
        }
        int[] array = new int[n];
       for(int i=0; i<n; i++){
           array[i] = sc.nextInt();
       }
        Arrays.sort(array);
       
        for(int j=0; j<n; j++){
           boolean flag = true;
            while(flag){
                 if(array[j]<array[n-1]){
                    flag = true;
                 }else if(array[j]==array[n-1]){
                    flag = false;  
                 }else{
                   System.out.println("NO"); 
                     return;
                 }
                array[j] = array[j]*2;
            }
        }
        System.out.println("YES");
        return;
    }
}

发表于 2018-09-27 19:45:25 回复(0)
先排序,然后从最低位开始排查,若和后一位相等,则继续,若不等,则检查加倍后是否相等,依次往后排查直到最后。中间若有一次不满足则输出NO,否则输出YES

public class Main4 {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i]=scanner.nextInt();
        }
         
        Arrays.sort(nums);        //排序
        
        for(int i=0;i<n-1;i++){
            if(isOK(nums[i], nums[i+1]))
                continue;
            else{
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
        scanner.close();
        
    }
    
    public static boolean isOK(int m,int n){
        if(m==n)
            return true;
        while(m<n){
            m*=2;
            if(m==n)
                return true;
        }
        return false;
    }
}

发表于 2018-05-15 10:50:26 回复(0)

热门推荐

通过挑战的用户