# 一道编程题——lucky triples

Published On 四月 11, 2017

category algorithm

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

# Languages

To provide a Python solution, edit solution.py To provide a Java solution, edit solution.java

# 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

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

## 解法

### 暴力解

l的长度不超过2000，一种简单暴力的解法是遍历所有的三元组，判断是否满足整除的条件。

def answer(l):
count = 0
length = len(l)
if length < 3:
return 0
l = sorted(l)
for i in range(length-2):
for j in range(i+1, length-1):
if l[j] % l[i] == 0:
for k in range(j+1, length):
if l[k] % l[j] == 0:
count = count + 1
return count


### 解法二（failed）

# the number of combinations
import operator
def combin(n,k):
if n<k:
return 0
if k==n:
return 1
if k > n/2:
k=n-k
return  reduce(operator.mul, range(n - k + 1, n + 1)) /reduce(operator.mul, range(1, k +1))


• 对于不同的i，如果c[i]>=3，则计算c(c[i],3)
• 对于不同的j(j>i)，如果j%i==0并且c[i]+c[j]>=3，则计算c(c[i]+c[j],3)-c(c[i],3)-c(c[j],3)，why?类似从2个盒子里取3个球，要求每个盒子至少取一个球的问题
• 对于不同的k(k>j>i)，如果k%j==0,j%i==0，则有c[i]*c[j]*c[k]

def answer(l):
count = 0
length = len(l)
if length < 3:
return 0
c = {}
for i in l:
c[i] = 0
for i in l:
c[i] = c[i]+1

l = sorted(l)
L=[l[0]]
for i in range(1,length):
if l[i]==l[i-1]:
continue
L.append(l[i])
length = len(L)
# pdb.set_trace()
for i in range(length):
ci=c[L[i]]
if ci>=3:
count = count + ci*(ci-1)*(ci-2)/6
for j in range(i+1,length):
if L[j]%L[i]:
continue
cj=c[L[j]]
s=ci+cj
if s>=3:
# count = count + ci*cj+(ci-1)*(cj-1)
count = count + s*(s-1)*(s-2)/6
if ci>=3:
count = count - ci*(ci-1)*(ci-2)/6
if cj>=3:
count = count - cj*(cj-1)*(cj-2)/6
for k in range(j+1, length):
if L[k]%L[j]:
continue
ck=c[L[k]]
count=count+ci*cj*ck
return count


#pick 3 balls from 3 box, how many combinations？
#balls in the same box are exactly the same
#two balls from different box are different from each other
def combine2(a,b=0,c=0):
count = 0
if a+b+c<3:
return 0
for i in range(4):
if i>a:
continue
for j in range(4-i):
if j>b or 3-i-j>c:
continue
count=count+1
return count


1 1,2 1,2,3

# only count different tuple
count = 0
length = len(l)
if length < 3:
return 0
c = {}
for i in l:
c[i] = 0
for i in l:
c[i] = c[i]+1

l = sorted(l)
L=[l[0]]
for i in range(1,length):
if l[i]==l[i-1]:
continue
L.append(l[i])
length = len(L)
# pdb.set_trace()
for i in range(length):
ci=c[L[i]]
for j in range(i+1,length):
if L[j]%L[i]:
continue
cj=c[L[j]]
for k in range(j+1, length):
if L[k]%L[j]:
continue
ck=c[L[k]]
count=count+1
if ci>1:
count = count + 1
if cj>1:
count = count + 1
if ci>=3:
count = count + 1
return count


### 解法三（time exceeds）

counts the number of "lucky triples" of (lst[i], lst[j], lst[k]) where i < j < k

oh,my god!原来排序是我噩梦的开始。原来一切都是因为我读题不认真。 比如输入是[2, 1, 4]，上面的程序会得到1，而正确答案是0。

def answer(l):
count = 0
length = len(l)
if length < 3:
return 0
d = []
i = 0
while i < length:
c = 1
while i+c < length and l[i+c] == l[i]:
c = c + 1
d.append((l[i], c))
i = i + c
# pdb.set_trace()
length = len(d)
for i in range(length):
iv,ic = d[i]
if ic>=3:
count = count + ic*(ic-1)*(ic-2)/6
for j in range(i+1,length):
jv,jc=d[j]
if jv%iv:
continue
s=ic+jc
if s>=3:
count = count + s*(s-1)*(s-2)/6
if ic>=3:
count = count - ic*(ic-1)*(ic-2)/6
if jc>=3:
count = count - jc*(jc-1)*(jc-2)/6
for k in range(j+1, length):
kv,kc = d[k]
if kv%jv:
continue
count=count+ic*jc*kc
return count


1,2,1,2,1,2....


# improve answer above
count = 0
length = len(l)
if length < 3:
return 0
d = []
i = 0
while i < length:
c = 1
while i+c < length and l[i+c] == l[i]:
c = c + 1
d.append((l[i], c))
i = i + c

m = {}
length = len(d)
for i in range(length):
m[i] = []
iv, ic = d[i]
for j in range(i+1,length):
jv,jc=d[j]
if jv%iv==0:
m[i].append(j)

for i in range(length):
iv,ic = d[i]
if ic>=3:
count = count + ic*(ic-1)*(ic-2)/6
for j in m[i]:
jv,jc=d[j]
s=ic+jc
if s>=3:
count = count + s*(s-1)*(s-2)/6
if ic>=3:
count = count - ic*(ic-1)*(ic-2)/6
if jc>=3:
count = count - jc*(jc-1)*(jc-2)/6
for k in m[j]:
kv,kc = d[k]
count=count+ic*jc*kc
return count


### 最终解

def answer(l):
count = 0
length = len(l)
if length < 3:
return 0
# m = [[]] * length
m=[]
for i in range(length):
m.append([])
for i in range(length):
for j in range(i+1, length):
if l[j] % l[i] == 0:
m[i].append(j)
for divs in m:
count = count + sum([len(m[div]) for div in divs])
return count


if __name__ == '__main__':
from test_func import test

input1=([1]*1999)
input1.append(999999)
[
([],0),
([1],0),
([1,2],0),
([1,2,3],0),

([1,2,4],1),
([1,1,1],1),

([2,1,4],0),

([2,2,2,3],1),
([1,1,1,2],4),

([1,1,2,3],2),
([3,2,2,4],1),
([1,2,2,2],4),
([2,2,4,4,1,1],4),

([1,1,1,1,1,1,1,1,1,1],120),
([1,2,4,8,16],10),

([1,2,3,4,5,6],3),

([1 for i in range(1000)],166167000),
([1 for i in range(2000)],1331334000),
([i+1 for i in range(1000)],16287),
([i+1 for i in range(2000)],40888),
([i+1000000 for i in range(1000)],0),
([1,2]*1000,665667000),# time limit exceeded
(input1, 1331334000)
]
)


+---------------------------------+---------+------------+--------+--------+
|              func               | time(s) |   result   | expect | status |
+=================================+=========+============+========+========+
| answer([])                      | 0.000   | 0          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1])                     | 0.000   | 0          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2])                  | 0.000   | 0          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 3])               | 0.000   | 0          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 4])               | 0.000   | 1          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 1, 1])               | 0.000   | 1          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([2, 1, 4])               | 0.000   | 0          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([2, 2, 2, 3])            | 0.000   | 1          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 1, 1, 2])            | 0.000   | 4          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 1, 2, 3])            | 0.000   | 2          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([3, 2, 2, 4])            | 0.000   | 1          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 2, 2])            | 0.000   | 4          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([2, 2, 4, 4, 1, 1])      | 0.000   | 4          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 1, 1, ..., 1, 1, 1]) | 0.000   | 120        |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 4, 8, 16])        | 0.000   | 10         |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 3, 4, 5, 6])      | 0.000   | 3          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 1, 1, ..., 1, 1, 1]) | 0.142   | 166167000  |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 1, 1, ..., 1, 1, 1]) | 0.566   | 1331334000 |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 3, ...999, 1000]) | 0.046   | 16287      |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 3, ...999, 2000]) | 0.191   | 40888      |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1000000, ..., 1000999]) | 0.047   | 0          |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 2, 1, ..., 2, 1, 2]) | 0.485   | 665667000  |        | √      |
+---------------------------------+---------+------------+--------+--------+
| answer([1, 1, 1, ...1, 999999]) | 0.560   | 1331334000 |        | √      |
+---------------------------------+---------+------------+--------+--------+
all 23 test(s) passed