Python - Tìm phần tử chia mảng thành hai mảng con có tích bằng nhau

Giả sử chúng ta có mảng kích thước N; chúng ta phải tìm một phần tử chia mảng thành hai mảng con khác nhau có tích bằng nhau. Trả về -1 nếu không thể phân hoạch.

Ví dụ, nếu đầu vào là [2,5,3,2,5], thì đầu ra là 3, hai mảng con: {2,5} và {2,5}.

Giải pháp:

• n := độ dài mảng
• multiply_pref: mảng tích tiền tố, multiply_pref[0] = array[0]
• for i=1..n-1: multiply_pref[i] = multiply_pref[i-1]*array[i]
• multiply_suff: mảng tích hậu tố, multiply_suff[n-1] = array[n-1]
• for i=n-2..0: multiply_suff[i] = multiply_suff[i+1]*array[i]
• for i=1..n-2: nếu multiply_pref[i] == multiply_suff[i] thì trả về array[i]
• Trả về -1

Ví dụ Code

def search_elem(array):
    n = len(array)
    multiply_pref = []
    multiply_pref.append(array[0])
    for i in range(1, n):
        multiply_pref.append(multiply_pref[i-1]*array[i])
    multiply_suff = [None for i in range(0, n)]
    multiply_suff[n-1] = array[n-1]
    for i in range(n-2, -1, -1):
        multiply_suff[i] = multiply_suff[i+1]*array[i]
    for i in range(1, n-1):
        if multiply_pref[i] == multiply_suff[i]:
            return array[i]
    return -1

array = [2,5,3,2,5]
print(search_elem(array))

Đầu vào

[2,5,3,2,5]

Đầu ra

3