Nathaniel Wilson - 1 year ago 1515
Java 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

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

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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download