题目来自
https://www.nowcoder.com/questionTerminal/c55f4f15cc3f4ff0adede7f9c69fa0c1
这是小米面试时考官给出的一道题。面试结束之后想了下，这不就是判断一个数是否是 2 的次方倍吗。我之前还做过判断关于指数幂的问题。
题目介绍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 牛牛有一个数组，里面的数可能不相等，现在他想把数组变为：所有的数都相等。问是否可行。
牛牛可以进行的操作是：将数组中的任意一个数改为这个数的两倍。
这个操作的使用次数不限，也可以不使用，并且可以对同一个位置使用多次。
输入描述:
输入一个正整数N (N <= 50)
接下来一行输入N个正整数，每个数均小于等于1e9.
输出描述:
假如经过若干次操作可以使得N个数都相等，那么输出 `"YES"`, 否则输出 `"NO"`
示例1
输入
2
1 2
输出
YES
|
题目分析
既然最后全部的数都相等，那说明数组中的任意两个数A，B（A >= B），一定满足
1
2
| A % B == 0 可以被整除
(A / B) & (A / B - 1) == 0 商为2的倍数
|
那如何判断 B 是 A 的二次倍数呢？
我们利用二进制位运算的特点
1
2
3
4
5
6
7
| // 等于 0 则说明是2的幂方
// 比如
// 4 100
// &
// 2 010
// = 000
n & (n - 1) == 0
|
我们只需要每次对 两个数 进行判断，如果成立，则返回 YES
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public boolean yesOrNot(int [] intarrs) {
for ( int i = 0 ; i < intarrs.length - 1; i ++) {
if(!isOk(intarrs[i],intarrs[i + 1])) {
System.out.println("NO");
return false;
}
}
System.out.println("YES");
return true;
}
public boolean isOk(int num1, int num2) {
int more = num1, less = num2 ;
if (num1 < num2){
more = num2;
less = num1;
}
if (more % less == 0 && ((more / less) & (more / less - 1)) == 0) {
return true;
}
return false;
}
|