I am trying to solve the following problem:
Write a function solution(l) that takes a list of positive integers l and counts the number of "lucky triples" of (li, lj, lk) where the list indices meet the requirement i < j < k. The length of l is between 2 and 2000 inclusive. A "lucky triple" is a tuple (x, y, z) where x divides y and y divides z, such as (1, 2, 4). The elements of l are between 1 and 999999 inclusive. The solution 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 solution 3 total.
My solution only passes the first two tests; I am trying to understand what it is wrong with my approach rather then the actual solution. Below is my function for reference:
def my_solution(l):
from itertools import combinations
if 2<len(l)<=2000:
l = list(combinations(l, 3))
l= [value for value in l if value[1]%value[0]==0 and value[2]%value[1]==0]
#l= [value for value in l if (value[1]/value[0]).is_integer() and (value[2]/value[1]).is_integer()]
if len(l)<0xffffffff:
l= len(l)
return l
else:
return 0
CodePudding user response:
If you do nested iteration of the full list and remaining list, then compare the two items to check if they are divisors... the result counts as the beginning and middle numbers of a 'triple',
then on the second round it will calculate the third... All you need to do is track which ones pass the divisor test along the way.
For Example
def my_solution(l):
row1, row2 = [[0] * len(l) for i in range(2)] # Tracks which indices pass modulus
for i1, first in enumerate(l):
for i2 in range(i1 1, len(l)): # iterate the remaining portion of the list
middle = l[i2]
if not middle % first: # check for matches
row1[i2] = 1 # increment the index in the tracker lists..
row2[i1] = 1 # for each matching pair
result = sum([row1[i] * row2[i] for i in range(len(l))])
# the final answer will be the sum of the products for each pair of values.
return result