一、核心思路深度拆解
要解决这个问题,我们首先要明确“最多能执行多少次全体除以2”的本质:
每次操作要求所有数都是偶数,等价于“所有数都能被2整除”。每执行一次操作,所有数都除以2,相当于对每个数的“2的幂次”减1。
当某一个数的“2的幂次”被减到0时(即该数变成奇数),就无法继续操作。因此:
最大操作次数 = 数组中每个数包含的“2的因子个数”的最小值。
举个直观的例子:
假设数组是 [8, 12, 40]:
* 8的2的因子个数:8 ÷2=4 → 4÷2=2 → 2÷2=1(共3次),即3个2;
* 12的2的因子个数:12÷2=6 →6÷2=3(共2次),即2个2;
* 40的2的因子个数:40÷2=20→20÷2=10→10÷2=5(共3次),即3个2;
操作1次后:[4,6,20](所有数仍为偶数,因为每个数的2的因子个数≥1);
操作2次后:[2,3,10](此时12的2的因子已耗尽,3是奇数,无法继续);
因此最多操作2次,恰好是所有数2的因子个数的最小值。
二、代码逐行详细解释(带底层逻辑)
三、样例全流程模拟
样例1:输入 3 8 12 40
1. 初始化:n=3,mi=200;
2. 第一次循环(i=1):
* 读取a=8,cnt=0;
* 8%2=0 → cnt=1,a=4;
* 4%2=0 → cnt=2,a=2;
* 2%2=0 → cnt=3,a=1;
* 1%2≠0 → 退出循环;
* cnt=3 < mi=200 → mi=3;
3. 第二次循环(i=2):
* 读取a=12,cnt=0;
* 12%2=0 → cnt=1,a=6;
* 6%2=0 → cnt=2,a=3;
* 3%2≠0 → 退出循环;
* cnt=2 < mi=3 → mi=2;
4. 第三次循环(i=3):
* 读取a=40,cnt=0;
* 40%2=0 → cnt=1,a=20;
* 20%2=0 → cnt=2,a=10;
* 10%2=0 → cnt=3,a=5;
* 5%2≠0 → 退出循环;
* cnt=3 ≥ mi=2 → mi不变;
5. 输出mi=2 → 符合样例结果。
样例2:输入 4 5 6 8 10
1. 初始化:n=4,mi=200;
2. 第一次循环(i=1):
* 读取a=5,cnt=0;
* 5%2≠0 → 退出循环;
* cnt=0 < mi=200 → mi=0;
3. 后续循环(i=2/3/4):
* 6的cnt=1、8的cnt=3、10的cnt=1,均≥mi=0 → mi保持0;
4. 输出mi=0 → 符合样例结果。
四、关键细节与易错点
1. mi的初始值:
* 初始值要足够大(如200),确保第一次比较时能被第一个数的cnt替换;
* 若初始值设为0,会导致所有cnt都≥0,结果永远是0,错误。
2. a的更新:
* 必须在循环内执行a /= 2,否则a永远是初始值,循环无限执行;
3. 奇数的处理:
* 奇数的a%2=1,循环直接退出,cnt=0,这是正确的(奇数没有2的因子)。
五、扩展思考(为什么是“最小值”而非“最大值/平均值”)
* 最大值:若取最大值(如样例1的3),但第二个数12只能支撑2次操作,第3次操作时12已变成3(奇数),无法执行;
* 平均值:无实际意义,操作的前提是“所有数都满足条件”,只要有一个数不满足,就无法操作。
因此,只有最小值能准确反映所有数共同能支撑的最大操作次数。