解法
- 最終的な値が入力の最大値を超えることはない。
- aとbが一致するまで大きい方を1/2ずつしていった時の最終的な値をM(a,b)とすると、最終的な値はM(a0,a1,a2,...)を2の累乗倍したものである。
コード
import java.util.Scanner;
public class Main {
public void solve() {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] a = new int[N];
int minMatch = 1;
int max = 0;
for (int i = 0; i < N; i++) {
a[i] = scanner.nextInt();
if (i == 0) {
minMatch = a[0];
} else {
minMatch = getmatch(minMatch, a[i]);
}
max = Math.max(max, a[i]);
}
scanner.close();
int minSteps = Integer.MAX_VALUE;
for (int finalValue = minMatch; finalValue <= max; finalValue <<= 1) {
int steps = 0;
for (int i = 0; i < N; i++) {
steps += steps(a[i], finalValue);
}
minSteps = Math.min(minSteps, steps);
}
System.out.println(minSteps);
}
private int steps(int x, int y) {
int ret = 0;
int prematch = getmatch(x, y);
while (x > prematch) {
ret++;
x >>= 1;
}
while (y > prematch) {
ret++;
y >>= 1;
}
return ret;
}
private int getmatch(int a, int b) {
while (a != b) {
if (a > b)
a >>= 1;
else
b >>= 1;
}
return a;
}
public static void main(String[] args) {
new Main().solve();
}
}