Google Foobar Level 3 - Lucky Triples (Find the Access Codes)

Question

I have been working on this problem for 3 days now. I wrote a piece of java code that works perfectly on my machine testing in Eclipse, but when I put it in Foobar, it either returns "Error(400) Bad Request" or "Took too long to execute" or something else.

To quote it from this other question of the same Foobar question, the prompt of the challenge is essentially:

Given a list (from 1 to 2000 elements) of random integers (from 1 to 999999) write a function, answer(l) that accepts a list as input and returns the number of "lucky triples" present in the list.

For this purpose, a lucky triple is defined as a list of three numbers \$(x, y, z)\$ such that \$x\$ divides \$y\$, \$y\$ divides \$z\$, and \$x \le y \le z\$. So, for instance, \$(2, 4, 8)\$ is a lucky triple and so is \$(1, 1, 1)\$.

Test cases:

input: [1, 1, 1] ouput: 1

input: [1, 2, 3, 4, 5, 6] output: 3

---

public static int answer(int[] l) { 
    ArrayList<ArrayList<Integer>> log = new ArrayList();
    for(int i1=0; i1 < l.length; i1++){
        for(int i2=i1+1; i2 < l.length; i2++){
            for(int i3=i2+1; i3 < l.length; i3++){
                if(l[i3]%l[i2]==0 && l[i2]%l[i1]==0 && !log.contains(new ArrayList<>(Arrays.asList(l[i1], l[i2], l[i3])))){
                    log.add(new ArrayList<>(Arrays.asList(l[i1], l[i2], l[i3])));
                }
            }
        }
    }
    return log.size();
}

My idea is to generate all the possible combinations number by number and see if that combination satisfies the divisible situation, and whether it has been already recorded, if not, then record the set of numbers in a "log". Then return the size of the log. Like I said, this piece of code runs perfectly on my own machine. So I wonder if it is a performance issue.

Answer 1

Optimizing this algorithm

                if(l[i3]%l[i2]==0 && l[i2]%l[i1]==0 && !log.contains(new ArrayList<>(Arrays.asList(l[i1], l[i2], l[i3])))){

I have two problems with this section of code.

First, in l[i2]%l[i1]==0, this will return the same result regardless of the value of i3. So why is it inside the i3 loop? It could be before that loop and skip the loop if not true.

Second, you use List.contains with an arbitrarily long list. The longer the list, the slower that method is. Consider using a HashSet instead. Then the speed remains constant relative to the size.

With these two changes:

    public static int answer(int[] l) {
        Set<List<Integer>> log = new HashSet<>();
        for (int i1 = 0; i1 < l.length; i1++) {
            for (int i2 = i1 + 1; i2 < l.length; i2++) {
                if (l[i2] % l[i1] != 0) {
                    continue;
                }

                for (int i3 = i2 + 1; i3 < l.length; i3++) {
                    if ((l[i3] % l[i2] == 0)) {
                        log.add(Arrays.asList(l[i1], l[i2], l[i3]));
                    }
                }
            }
        }

        return log.size();
    }

Now you only check the third element if the first two elements are divisible.

And now, instead of using List.contains, you simply rely on the uniqueness of elements of a Set.

I also switched to use the interfaces as the types for log rather than the implementation. This allows me to skip the new ArrayList operations altogether.

I'm not crazy about the variable names either, but I didn't try to change them.

Assumptions

Both your original and this variant assume that the list is sorted in ascending order.

Custom datatype

This solution probably takes longer for small result sets, because HashSet is often higher overhead than List. You may be able to reduce the overhead by declaring your own type and providing an optimized hashCode method for it. Or the compiler may have already optimized it. You'll have to benchmark to be sure.