1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#!/usr/bin/python2
# Find the Access Codes
# =====================
# In order to destroy Commander Lambda's LAMBCHOP doomsday device, you'll need
# access to it. But the only door leading to the LAMBCHOP chamber is secured
# with a unique lock system whose number of passcodes changes daily. Commander
# Lambda gets a report every day that includes the locks' access codes, but
# only she knows how to figure out which of several lists contains the access
# codes. You need to find a way to determine which list contains the access
# codes once you're ready to go in.
# Fortunately, now that you're Commander Lambda's personal assistant, she's
# confided to you that she made all the access codes "lucky triples" in order
# to help her better find them in the lists. A "lucky triple" is a tuple (x, y,
# z) where x divides y and y divides z, such as (1, 2, 4). With that
# information, you can figure out which list contains the number of access
# codes that matches the number of locks on the door when you're ready to go in
# (for example, if there's 5 passcodes, you'd need to find a list with 5 "lucky
# triple" access codes).
# 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. 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
# ==========
# Your code should pass the following test cases.
# Note that it may also be run against hidden test cases not shown here.
# Input:
# solution.solution([1, 2, 3, 4, 5, 6])
# Output:
# 3
# Input:
# solution.solution([1, 1, 1])
# Output:
# 1
## O(n^2)
def solution(l):
c = [0] * len(l)
count = 0
for i in range(0, len(l)):
for j in range(0, i):
if l[i] % l[j] == 0:
c[i] = c[i] + 1
count = count + c[j]
return count
## O(n^3)
def solution2(l):
c = 0
while len(l) > 2:
t = l[1:]
for id,i in enumerate(t):
if i % l[0] == 0:
for j in t[(id + 1):]:
if j % i == 0:
c += 1
l = l[1:]
return c
## Way too much memory, it's not even funny
## python is supposed to do list comprehension in a good way, lol
## adapted from https://oeis.org/A333885
def solution3(l):
return len([(i, j, k)
for id,i in enumerate(l)
for jd,j in enumerate(l[(id+1):])
for k in l[(id+jd+2):]
if j%i==0 and k%j==0])
def solve(l):
print(l)
print(solution(l))
solve([1, 2, 3, 3, 5, 2])
solve([1, 2, 3, 4, 5, 6])
solve([1, 2, 3, 3, 2, 1])
solve([1 for x in xrange(2000)])
solve([1, 1, 1])
solve([])
solve([2])
solve([2, 5])
solve([1, 5, 6])
solve([1, 999999, 2])
|
