首页 > 试题广场 >

数组变换

[编程题]数组变换

热度指数：3781 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛有一个数组，里面的数可能不相等，现在他想把数组变为：所有的数都相等。问是否可行。
牛牛可以进行的操作是：将数组中的任意一个数改为这个数的两倍。

这个操作的使用次数不限，也可以不使用，并且可以对同一个位置使用多次。

数据范围：数组大小满足 $1 \le n \le 50 \$ ，数组中的数满足 $1 \le val \le 10^{9} \$

输入描述:

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

输出描述:

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

示例1

输入

2
1 2

输出

YES

示例2

输入

3
1 2 3

输出

NO

算法知识视频讲解

C/C++

渣_渣_渣

看着上面的回答改的，找出最大数，除各个数，能除尽并且结果全部是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)

Hasaki灬

#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)

C/C++

剩一口

追求极致，不盲目参考别人代码，容易限制自己思维，精简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)

→①年前↑

把数组每一个元素都除以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)

牛客8017644号

此题知识点应该是考如何判断一个整数是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)

非白羊

#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)

C/C++

pein531

从最大元素开始尝试，检查将所有元素变为target可不可行。对于给定的target，要想某个元素a变成它，首先target要能被a整除，其次target要是a的2的k次方倍（判断一下target/a的二进制中是否只有一个1即可）。

由于只能进行乘以2的操作，当没有办法使得所有元素变为target时，要将target乘以2继续尝试。

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
int n, a[N];

bool check(int ub) {
    for(int i = 0; i < n; i++) {
        if(ub % a[i] || __builtin_popcount(ub / a[i]) > 1) return false;
    }
    return true;
}

int main() {
    scanf("%d", &n);
    int mx = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        mx = max(mx, a[i]);
    }
    if(mx&1) mx <<= 1;
    bool flag = false;
    while(mx <= INT_MAX >> 1) {
        if(check(mx)) {
            flag = true;
            break;
        }
        mx <<= 1;
    }
    if(flag) puts("YES");
    else puts("NO");
    return 0;
}

发表于 2023-02-02 17:26:29 回复(0)

牛客375006号

#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)

caicaiya

lines = readLines("stdin")
for (l in lines[-1]) {
    if (l == "") {
        break;
    }
    ll = strsplit(l, " ")[[1]]
    a=length(unique(log2(as.numeric(as.numeric(ll)))%%1))==1
    cat(ifelse(a,'YES','NO'));
    cat('\n');
}

发表于 2024-01-21 14:07:58 回复(0)

mamong

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int a[50];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    bool result = true;
    for(int i=0;i<n;i++){
        while ((a[i] & 1) == 0) {
            a[i] = a[i] >> 1;
        }
        if (i > 0 && a[i] != a[i-1]) {
            result = false;
            break;
        }
    }
    printf(result?"YES":"NO");
}

发表于 2023-07-28 18:15:11 回复(0)

C/C++

一位专业不是计算机的大学生

先数组排序，然后两两比较，相等下一个，不相等，用大的 / 小的，再模2 等于0这两个数就可以通过操作成为相等的，

bool yesorno(int x ,int y)
{
     
    if((y/x)%2 == 0 || x==y)
    {
        return true;
    }
    return false;
}
int main() {
    int n;
    cin>>n;
    vector<int> tmp(n);
    for(int i = 0;i<n;i++)
    {
        cin>>tmp[i];
    }
    sort(tmp.begin(),tmp.end());
    for(int i = 0;i < n-1;i++)
    {
        if(!yesorno(tmp[i], tmp[i+1]))
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

发表于 2023-06-08 11:53:31 回复(0)

Cindy_Luo

import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        if(length == 1){
            System.out.println("YES");
            return;
        }
        int[] nums = new int[length];
 
        for(int i = 0; i < length; i++){
            nums[i] = sc.nextInt();
        }
 
        String str = "YES";
                // 两层循环暴力求解
        for(int i = 0; i < length; i++){
            int temp = nums[i];
            for(int j = i+1; j < length; j++){
                if(temp < nums[j]){
                    if((nums[j] / temp) %2 != 0){
                        str = "NO";
                        break;
                    }
                }else if(temp > nums[j]){
                    if((temp / nums[j]) %2 != 0){
                        str = "NO";
                        break;
                    }
                }else{
                    continue;
                }
            }
            if(str.equals("NO")){
                break;
            }
        }
        System.out.println(str);
    }
}

发表于 2022-08-31 10:11:11 回复(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)

牛客565723807号

这题目是啥意思，完全没看懂

一个数组，里面的数可能不相等，现在他想把数组变为：所有的数都相等。问是否可行。

大佬们提交代码的时候，能不能帮忙解答一下题目的意思，感谢感谢

看了上面评论的，和这个题目好像没啥关系

发表于 2021-11-15 10:27:43 回复(1)

牛客461121626号

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)

十一月的may

#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)