Google Foobar Challenge 3 - Find the Access Codes
<h1>Find the Access Codes</h1>

<p>Write a function answer(l) that takes a list of positive integers l and counts the number of "lucky triples" of (lst[i], lst[j], lst[k]) where i &lt; j &lt; k.  The length of l is between 2 and 2000 inclusive.  The elements of l are between 1 and 999999 inclusive.  The answer fits within a signed 32-bit integer. Some of the lists are purposely generated without any access codes to throw off spies, so if no triples are found, return 0. </p>

<p>For example, [1, 2, 3, 4, 5, 6] has the triples: [1, 2, 4], [1, 2, 6], [1, 3, 6], making the answer 3 total.</p>

<h1>Test cases</h1>

<p>Inputs:
    (int list) l = [1, 1, 1]
Output:
    (int) 1</p>

<p>Inputs:
    (int list) l = [1, 2, 3, 4, 5, 6]
Output:
    (int) 3</p>

<h1>My Attempt</h1>

<pre><code>from itertools import combinations

def answer(l):
    if len(l) &lt; 3:
        return 0
    found = 0
    for val in combinations(l,3):
        # Ordering Check
        if (val[0] &lt;= val[1] &lt;= val[2]) != True:
            continue
        # Answer Size Check against size of signed integer 32 bit
        if int(val[0].__str__() + val[1].__str__() + val[2].__str__()) &gt; 2147483647:
            continue
        # Division Check
        if (val[1] % val[1] != 0) or (val[2] % val[1] != 0):
            continue
        # Increment 'found' variable by one
        found += 1
    return found
</code></pre>

<p>Here is a solution off the top of my head that has O(n^2) time and O(n) space complexity. I think there is a better solution (probably using dynamic programming), but this one beats generating all combinations.</p>

<pre><code>public static int foobar( int[] arr)
{
    int noOfCombinations = 0;
    int[] noOfDoubles = new int[arr.length];

    // Count lucky doubles for each item in the array, except the first and last items
    for( int i = 1; i &lt; arr.length-1; ++i)
    {
        for( int j = 0; j &lt; i; ++j)
        {
            if( arr[i] % arr[j] == 0)
                ++noOfDoubles[i];
        }
    }

    // Count lucky triples
    for( int i = 2; i &lt; arr.length; i++)
    {
        for( int j = 1; j &lt; i; ++j)
        {
            if( arr[i] % arr[j] == 0)
                noOfCombinations += noOfDoubles[j];
        }
    }

    return noOfCombinations;
}
</code></pre>

java python combinations