首页 > 试题广场 >

数组变换

[编程题]数组变换
  • 热度指数：4454 时间限制：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
算法知识视频讲解
添加回答
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号头像 牛客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)
Hasaki灬头像 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)
大佬求代头像 大佬求代 
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
            int n = in.nextInt();
            int[] a = new int[n];
            int max = 0;
            for(int i=0;i<n;i++){
                a[i] = in.nextInt();
                max = Math.max(max,a[i]);
            }
            for(int i =0;i<n;i++){
                //解法一:
                if(max % a[i] !=0){
                    System.out.println("NO");
                    return ;
                }
                //解法二:
                // int tmp = (max/a[i]);
                // if( a[i] !=max && tmp%2 != 0){
                //     System.out.println("NO");
                //     return ;
                // }
            }
            System.out.println("YES");
    }
}

我觉得:牛客少了一些测试数据判断正确性
比如:
2
3 9
对于解法一,很明显是不对的,对于这个测试用例他返回的是YES,解法二返回的是NO,但是分别提交解法一和解法二,他的结果都能通过所有测试用例,希望牛客官方看到了能完善一下后台的数据集

发表于 2025-07-05 07:34:36 回复(0)
C/C++
pein531头像 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号头像 牛客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)
C/C++
渣_渣_渣头像 渣_渣_渣
  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)
大时代1105头像 大时代1105

思路

贪心 + 位运算

过程

图片说明

代码

#include <iostream>

using namespace std;

const int N = 60;
int a[N];
int n, maxVal;

bool check()
{
    for(int i = 0;i < n;i ++)
    {
        if(maxVal % a[i]) return false;
        int x = maxVal / a[i];
        if(x - (x & -x)) return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        cin >> a[i];
        if(a[i] > maxVal) maxVal = a[i];
    }
    if(check()) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}
发表于 2025-03-13 14:02:39 回复(0)
Man9o头像 Man9o

思路

用了几个例子思考了一下，操作只能乘以2或者不乘且次数不限，要求所有数字最终都相同。假设所有数字最终已经相同了，如x，那么它们肯定是2的某个次幂，那么变成x之前的任何数，都是x的因子。

原先更大的数，越接近最终的x，通过排序，就使得“因子”具有了传递性。遍历所有元素，如果前面的数不是后面的数的因子，那就不可以得到全部是x的序列，反之即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int a[N], n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i + 1] % a[i] != 0) 
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}
  • 时间复杂度：。
发表于 2024-08-02 11:12:21 回复(0)
白开水不加冰糖头像 白开水不加冰糖
思路：找出数组中的最大值，让nums[max]%数组中其他的数，余数为0则这个数可以变成相等的数，需要注意因为题目说明可能相等，所以nums[i]==nums[max]就不需要判断了 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 处理输入
        int n = in.nextInt();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) nums[i] = in.nextLong();
        // 排序找出最大值
        Arrays.sort(nums);
        for (int i = 0; i < n - 1; i++) {
            // 取余，如果！=0，直接return
            if (nums[i] != nums[n - 1] && nums[n - 1] % nums[i] != 0) {
                System.out.println("NO");
                return;
            }
        }
        // 当循环走完，则证明可以变换
        System.out.println("YES");
    }
}

发表于 2024-05-10 14:58:53 回复(0)
caicaiya头像 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头像 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头像 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号头像 牛客565723807号
这题目是啥意思，完全没看懂
一个数组，里面的数可能不相等，现在他想把数组变为：所有的数都相等。问是否可行。
大佬们提交代码的时候，能不能帮忙解答一下题目的意思，感谢感谢
看了上面评论的，和这个题目好像没啥关系
发表于 2021-11-15 10:27:43 回复(1)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 c#工程师 数据库工程师 信息技术岗 数学 Java工程师
来自：【2017】牛客模考（...
难度：
47条回答 17608浏览

热门推荐

通过挑战的用户

相关试题

数组变换

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号