数组迭代生成3的倍数问题：代码故障排查与正确解法咨询

题目描述 #

给定一个整数数组作为输入，数组大小为n。循环执行以下步骤，直到数组的前n-1个元素均为3的倍数：
对于数组索引i，从i=0开始遍历至i=n-2：将array[i]与array[i+1]相乘，若乘积可被3整除，则将array[i]替换为该乘积，否则不做修改。数组最后一个元素无配对元素，无需处理。返回使前n-1个元素均为3的倍数所需的循环次数，若无法实现则返回-1。

示例 #

示例1 #

输入：[34, 56, 20, 90, 100]
输出：3
解释：
迭代1：[34, 56, 1800, 9000, 100]
迭代2：[34, 100800, 16200000, 900000, 100]
迭代3：[3427200, 100800, 16200000, 90000000, 100]
因此迭代次数为3。

示例2 #

输入：[1, 333, 222, 22]
输出：1
解释：
迭代1：[333, 333, 222, 22]
此时前3个数字均为3的倍数，故迭代次数为1。

用户提交的Java代码 #

public class Main {

   public static int solve(int[] a) {
        int n = a.length;
        int rounds = 0;

        while (true) {
            boolean allMultiplesOfThree = true;

            // Check if the first n-1 elements are already multiples of 3
            for (int i = 0; i < n - 1; i++) {
                if (a[i] % 3 != 0) {
                    allMultiplesOfThree = false;
                    break;
                }
            }

            // If all first n-1 elements are multiples of 3, return the rounds count
            if (allMultiplesOfThree) {
                return rounds;
            }

            // Increment rounds and update the array in place
            rounds++;
            for (int i = 0; i < n - 1; i++) {
                int product = a[i] * a[i + 1];
                if (product % 3 == 0) {
                    a[i] = product;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] input1 = {34, 56, 20, 90, 100};
        System.out.println(solve(input1)); // Expected: 3

        int[] input2 = {1, 333, 222, 22};
        System.out.println(solve(input2)); // Expected: 1
    }
}

代码问题分析 #

该代码仅通过8个测试用例中的2个，问题主要集中在以下几点：

• 原地修改导致计算错误：每一轮更新数组时，修改a[i]会影响后续i+1位置的计算，但题目要求每一轮的更新必须基于上一轮的原始数组，而非修改后的数组。
• 整数溢出：多次相乘后数值会远超int范围，溢出后会导致%3的判断结果错误。
• 未处理无法实现的情况：如果某个位置右侧没有任何3的倍数，代码会进入死循环，永远无法返回-1。
• 效率低下：大数组场景下，多次循环遍历会触发超时，尤其是需要大量轮次的情况。

正确解法思路 #

不需要实际计算乘积，只需跟踪3的因子传递规律：

1. 一个元素能被3整除，要么本身包含3的因子，要么在某一轮中与右侧已被3整除的元素相乘。
2. 从右往左遍历数组，记录最近的能被3整除的元素位置：
   • 若当前元素本身是3的倍数，无需轮次。
   • 若右侧没有任何3的倍数，直接返回-1。
   • 否则，当前位置需要的轮数为最近3的倍数位置 - 当前索引（每一轮3的因子向左传递一位）。
3. 最终答案取所有位置所需轮数的最大值，因为要等待所有位置都变为3的倍数。

正确Java代码实现 #

public class Main {
    public static int solve(int[] a) {
        int n = a.length;
        if (n <= 1) {
            return 0; // 前n-1个元素为空，直接满足条件
        }

        int maxRounds = 0;
        int lastMultipleIndex = -1;

        // 从右往左遍历，计算每个位置需要的轮数
        for (int i = n-1; i >= 0; i--) {
            if (a[i] % 3 == 0) {
                lastMultipleIndex = i;
            }
            // 只处理前n-1个元素
            if (i < n-1) {
                if (lastMultipleIndex == -1) {
                    return -1; // 右侧无3的倍数，无法满足条件
                }
                int currentRounds = lastMultipleIndex - i;
                if (currentRounds > maxRounds) {
                    maxRounds = currentRounds;
                }
            }
        }

        return maxRounds;
    }

    public static void main(String[] args) {
        int[] input1 = {34, 56, 20, 90, 100};
        System.out.println(solve(input1)); // 输出3

        int[] input2 = {1, 333, 222, 22};
        System.out.println(solve(input2)); // 输出1

        // 测试无法实现的情况
        int[] input3 = {1,2,4,5};
        System.out.println(solve(input3)); // 输出-1
    }
}

内容的提问来源于stack exchange，提问作者CodeCrusader