consecutive pairs divisible by 3

The following problem was asked during an interview:

Given an array of integers as input, the size of an array is n.

Perform the below steps in a loop until the first n-1 items in the list are multiples of 3.

For an index of array i, start from i=0 and proceed till i=n-2: Multiply array[i] and array[i+1], if the product is divisible by 3, then replace array[i] with the product, otherwise do not change it.

The last item in the list cannot have a pair so no need to process it.

Return how many times the loop has run to make n-1 items in the list are multiples of 3. If solution is not possible then return -1

Example 1
Input: [34, 56, 20, 90, 100]
Output: 3
Explanation
Iteration 1: [34, 56, 1800, 9000, 100]
Iteration 2: [34, 100800, 16200000, 900000, 100]
Iteration 3: [3427200, 100800, 16200000, 90000000, 100]
Hence the number of iterations is 3.

Example 2
Input: [1, 333, 222, 22]
Output: 1
Explanation
Iteration 1: [333, 333, 222, 22]
The first 3 numbers are multiples of 3. Hence the number of iterations is 1.

Here is my code:

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
    }
}

There were 8 test cases. My code worked for only 2 test cases, while the remaining failed. The failed test cases are hidden, so I cannot see them, so I am not sure if they failed with the wrong output or timeout errors. Also if the values cannot fit in int we can use long to solve the problem.

What is the correct approach to solve this problem?

Solution

You can do this in one iteration.

We can observe that if we perform a multiplication and store the product, we have potentially made one more element in the array a multiple of 3. We can only make a new multiple of 3 if the next element is a multiple of 3. That means that if we have a few consecutive non-multiples of 3, we need as many iterations to "fix" that and make them all multiples of 3. Therefore the number to return is the size of the largest consecutive sequence of such non-multiples of 3.

There is one exception: if the last two elements of the input array are not multiples of 3, there is no way to make the one-but-last element a multiple of 3, and so there is no solution. It should be mentioned in the challenge what should be returned in that case.

This algorithm can be coded like this (I return -1 if there is no solution):

   public static int solve(int[] a) {
        if (a.length < 2) return 0; // Nothing to do
        if (a[a.length - 2] % 3 != 0 && a[a.length - 1] % 3 != 0) return -1; // No solution
        int nonMultiplesOf3 = 0;
        int result = 0;
        for (var value : a) {
            if (value % 3 != 0) {
                nonMultiplesOf3++;
                result = Math.max(result, nonMultiplesOf3);
            } else {
                nonMultiplesOf3 = 0;
            }
        }
        return result;
    }

The problem in your code

It doesn't deal with the boundary case, like with input {1, 1, 1, 1}. With that input your program will hang in an infinite loop.

Secondly, it takes the naive approach to actually make the iterations to be counted and performs all multiplications. But this is not efficient. In the worst case (when there is a solution), your algorithm will need 𝑛−1 iterations, where in each iteration the array is traversed. So this represents O(𝑛²) time complexity. If the testing platform sets a time limit on your program, then this might become an issue with large inputs that represent such a worst case.