Google Foobar Challenge 3 - Find the Access Codes

Question

Find the Access Codes

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 < j < 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.

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.

Test cases

Inputs: (int list) l = [1, 1, 1] Output: (int) 1

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

My Attempt

from itertools import combinations

def answer(l):
    if len(l) < 3:
        return 0
    found = 0
    for val in combinations(l,3):
        # Ordering Check
        if (val[0] <= val[1] <= 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__()) > 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

Answer 1

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.

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 < arr.length-1; ++i)
    {
        for( int j = 0; j < i; ++j)
        {
            if( arr[i] % arr[j] == 0)
                ++noOfDoubles[i];
        }
    }

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

    return noOfCombinations;
}

Answer 2

def solution(l):
    c = [0] * len(l)
    count = 0
    for i in range(0,len(l)):
        j=0
        for j in range(0, i):
            if l[i] % l[j] == 0:
                c[i] = c[i] + 1
                count = count + c[j]
    return count

This will take O(n^2) time complexity

To try it out just add these two lines as your driver code:

ar = [1, 2, 3, 4, 5, 6]
print(solution(ar))

Answer 3

Thing is: you let that library method combinations do all the "real" work for you.

And of course: normally that is exactly the way to go. You do not want to re-invent the wheel when there is an existing library function that gives you what you need. Your current code is pretty concise, and good to read (except maybe that you should call your list, well, "list", but not "l").

But this case is different: obviously, most of the execution time for this program will happen in that call. And it seems that google thinks whatever this call is doing .. can be done faster.

So, the answer for you is: you actually want to re-invent the wheel, by rewriting your code in a way that is better than what it is doing right now! A first starting point might be to check out the source code of combinations to understand if/how that call is doing things that you do not need in your context.

Guessing: that call creates a lot of permutations that are not ideal. All of that is wasted time. You want to step back and consider how to build those lucky triples from your input without creating a ton of not so lucky triples!

Answer 4

I tried implementing this in python. It isn't quite fast enough to pass the test, but it runs 50x faster then uoyilmaz's solution ported to python. The code for that is below:

#!/usr/bin/env python2.7

from bisect import insort_left
from itertools import combinations


def answer_1(l):
    """My own solution."""
    indices = {}
    setdefault_ = indices.setdefault
    for i, x in enumerate(l):
        setdefault_(x, []).append(i)

    out = 0
    highest_value = max(l)
    for i, x in enumerate(l):
        multiples = []
        for m in xrange(1, int(highest_value / x) + 1):
            if x * m in indices:
                for j in indices[x * m]:
                    if i < j:
                        insort_left(multiples, (j, x * m))

        if multiples:
            multiples = [m[1] for m in multiples]
            for pair in combinations(multiples, 2):
                out += pair[1] % pair[0] == 0

    return out


def answer_2(l):
    """@uoyilmaz's solution ported from Java."""
    out = 0
    pair_counts = [0] * len(l)
    for i in xrange(1, len(l) - 1):
        for j in xrange(i):
            if l[i] % l[j] == 0:
                pair_counts[i] += 1

    for i in xrange(2, len(l)):
        for j in xrange(1, i):
            if l[i] % l[j] == 0:
                out += pair_counts[j]

    return out


answer = answer_1

# -----------------------------------------------------------------------------

_SEED = 1.23


def benchmark(sample_count):
    from random import seed, randint
    import timeit
    clock = timeit.default_timer

    seed(_SEED)
    samples = [[randint(1, 999999) for _ in xrange(randint(2, 2000))]
                for _ in xrange(sample_count)]

    start = clock()
    for sample in samples:
        answer(sample)

    end = clock()
    print("%.4f s elapsed for %d samples." % (end - start, sample_count))


def test():
    # Provided test cases.
    assert(answer([1, 1, 1]) == 1)
    assert(answer([1, 2, 3, 4, 5, 6]) == 3)

    # Custom test cases.
    assert(answer([1]) == 0)
    assert(answer([1, 2]) == 0)
    assert(answer([2, 4]) == 0)
    assert(answer([1, 1, 1, 1]) == 4)
    assert(answer([1, 1, 1, 1, 1]) == 10)
    assert(answer([1, 1, 1, 1, 1, 1]) == 20)
    assert(answer([1, 1, 1, 1, 1, 1, 1]) == 35)
    assert(answer([1, 1, 2]) == 1)
    assert(answer([1, 1, 2, 2]) == 4)
    assert(answer([1, 1, 2, 2, 2]) == 10)
    assert(answer([1, 1, 2, 2, 2, 3]) == 11)
    assert(answer([1, 2, 4, 8, 16]) == 10)
    assert(answer([2, 4, 5, 9, 12, 34, 45]) == 1)
    assert(answer([2, 2, 2, 2, 4, 4, 5, 6, 8, 8, 8]) == 90)
    assert(answer([2, 4, 8]) == 1)
    assert(answer([2, 4, 8, 16]) == 4)
    assert(answer([3, 4, 2, 7]) == 0)
    assert(answer([6, 5, 4, 3, 2, 1]) == 0)
    assert(answer([4, 7, 14]) == 0)
    assert(answer([4, 21, 7, 14, 8, 56, 56, 42]) == 9)
    assert(answer([4, 21, 7, 14, 56, 8, 56, 4, 42]) == 7)
    assert(answer([4, 7, 14, 8, 21, 56, 42]) == 4)
    assert(answer([4, 8, 4, 16]) == 2)


def main():
    test()
    benchmark(100)


if __name__ == '__main__':
    main()

Now if anyone has an idea on how to speed this up further, I'm open for suggestions.

Answer 5

I actually just received this problem on foo.bar, so I'll provide insight into my O(n^2) solution.

I chose to model the input as a directed graph where each node in the graph is an index i into the input array and an edge from u to v exists if u can be divided by v.

Once I built the directed graph, it was just a matter of summing up all outgoing edges from each neighbor for each node. The correctness lies in the fact that a triplet exists when there is a path of length 3 in the constructed graph.

Node -> Neighbor -> # of ougoing edges = # of triplets starting from Node

Note: I used the indices of the input array for graph node values here but the input array values would also suffice since we are just counting up edges.

public static int answer(int[] l) {
    if (l.length < 3) {
        return 0;
    }

    Map<Integer, Set<Integer>> graph = new HashMap<>();
    graph.put(0, Collections.emptySet());

    for (int i = 1; i < l.length; i++) {
        graph.put(i, new HashSet<>());
        for (int j = 0; j < i; j++) {
            if (l[i] % l[j] == 0) {
                graph.get(i).add(j);
            }
        }
    }

    int count = 0;
    for (int node : graph.keySet()) {
        for (int neighbor : graph.get(node)) {
            count += graph.get(neighbor).size();
        }
    }

    return count;
}

Answer 6

I came across this question today on foobar as well. @saifeemustafaq gave a clever solution. I would just like to add some explanation to the answer. Hoping it could help someone like me.

   def solution(l):
        c = [0] * len(l)
        count = 0
        for i in range(len(l)):
            for j in range(i):
                if l[i] % l[j] == 0:
                    c[i] += 1
                    count += c[j]
        return count

The algorithm uses a nested for-loop structure. The outer loop works on every integer in the list, which is l[i]. The inner one finds out how many integers in the left-hand-side of l[i] can divide l[i]. The result will then be stored in a pre-created list.

The trickiest part is coming. Since j is always less than i, so every time when we look at l[i], the number of integers that can divide l[j] is already determined. Now that if l[j] divides l[i], lucky triples are found! l[j] divides l[i], and some other integers on the left-side of l[j] divide l[j]. The number of the lucky triples comprising l[j] and l[i] is exactly the number of integers that can divide l[j] in the storage list. This is why we have count += c[j] in the codes. When the loop finishes, we will have the answer.

Answer 7

1. Reverse iterate to count how many divisible factors before index i.
2. Reverse iterate again, and add up all the triples.

def solution(l):
    # Your code here
    n = len(l)
    cnt = [0] * n
    for i in range(n-1, -1, -1):
        for j in range(i):
            if l[i] % l[j] == 0:
                cnt[i] += 1
    ans = 0
    for i in range(n-1, -1, -1):
        for j in range(i):
            if l[i] % l[j] == 0:
                ans += cnt[j]
    return ans

s = solution([1,2,3,4,5,6])
print(s)