Làm sao để qua được test cuối bài maxPairProduct trên Codefights

[banhmisg9509 (Nguyễn Hùng)]

Đề yêu cầu tìm số lớn nhất x nằm trong mảng arr, điều kiện là có 2 số nữa cũng nằm trong arr mà tích của nó bằng x ( x = a*b ; x,a,b thuộc arr). Giờ phải sửa thuật toán làm sao để pass test cuối đây @.@

from collections import Counter
def maxPairProduct(a):
    m = Counter(a) # dict ( value : freq )
    a.sort()
    for i in reversed(a):
        for j in a:
            if (j > i) or (j > math.sqrt(i)):
                 break
            elif i % j == 0:
                r = i / j
                if r != j and m[r] > 0:
                    return i
                elif r == j and m[r] > 1:
                    return i
    return -1

[Gio (Gió)]

thay for j in a bằng for j in divisor(i) nó sẽ tiết kiệm thời gian hơn rất nhiều, hàm divisor(n) chỉ cần chạy đến sqrt(n)

[banhmisg9509 (Nguyễn Hùng)]

thằng divisor(i) nó dùng thế nào vậy bạn ? với lại mình cũng đã giới hạn nó chạy tới sqrt(i) rồi mà.

[Gio (Gió)]

divisor(n) là hàm sinh ra các ước <=sqrt(n), có thể được miêu tả:

divisor = lambda n: filter(lambda d: n%d==0, range(1,int(n**.5)+1))

cái hay ở đây là bạn không cần for j in a vì j,r có vai trò tương đương nhau, chỉ cần check m[j] tương tự như m[r] vậy. Chạy quá thời gian là do mảng a có tới 10⁵ phần tử trong khi sqrt(i) tối đa cũng chỉ 100 do max(a)<1E4

[nahi08 (NG)]

Em thấy chỗ này

if (j > i) or (j > math.sqrt(i)):

j>i suy ra j> math.sqrt(i)
bac chỉ cần giữ lại sqrt(i) thôi, bỏ đc 1 cái test logic
Cái nữa để ý đề, chiều dài list tận 105 mà gía trị chỉ có 104 là max, đoán là trùng số rất nhiều, dùng hàm set() lược bớt, bác đã gọi Counter thì xài Counter luôn,

for i in m:

em thấy hay hơn.

Em thử viết lại code của bác mà không cần dùng collections, chỉ cần set(list) thôi vẫn qua hết

def maxPairProduct(a):
    l = list(set(a))
    l.sort()
    lr = reversed(l)
    a_tri = sorted(a)
    for mpp in lr:
        s = math.sqrt(mpp)+1
        for div in [e for e in l if e<s]:
            if mpp%div == 0:
                if mpp/div in a_tri[a_tri.index(div)+1:]:
                    return mpp
    return -1

[banhmisg9509 (Nguyễn Hùng)]

He he cái này mình pass lâu rồi làm theo solution bác ở trên :v nhưng dù sao cũng cảm ơn.