【Python】配列を積が等しい2つの部分配列に分割する要素を見つける方法

問題の概要

サイズ N の配列が与えられたとき、その配列を積が等しい2つの部分配列に分割する要素を見つけます。そのような分割が不可能な場合は -1 を返します。

例えば、入力が [2,5,3,2,5] の場合、出力は 3 となります。このとき配列は {2, 5} と {2, 5} に分割され、それぞれの積はどちらも 10 で一致します。

解き方の考え方

この問題は、先頭からの累積積（プレフィックス積）と末尾からの累積積（サフィックス積）を事前に計算しておくことで効率的に解けます。各位置における左側の積と右側の積を即座に比較できるため、全体の計算量は O(N) に抑えられます。

具体的な手順は以下の通りです。

• n := 配列のサイズ
• multiply_pref := 新しいリスト（先頭からの累積積を格納）
• multiply_pref の末尾に array[0] を追加
• i が 1 から n-1 までの範囲で、以下を繰り返す：
  • multiply_pref の末尾に multiply_pref[i-1] × array[i] を追加
• multiply_suff := サイズ n のリストを作成し、すべて None で初期化（末尾からの累積積を格納）
• multiply_suff[n-1] := array[n-1]
• i が n-2 から 0 まで 1 ずつ減らしながら、以下を繰り返す：
  • multiply_suff[i] := multiply_suff[i+1] × array[i]
• i が 1 から n-2 までの範囲で、以下を繰り返す：
  • multiply_pref[i] と multiply_suff[i] が等しい場合：
    • array[i] を返す
• -1 を返す

実装例

理解を深めるために、以下の実装を見てみましょう。

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))

入力

[2,5,3,2,5]

出力

3

結果の解説

この例では、位置 2 の要素 3 を境に配列を分割すると、左側 {2, 5} の積（10）と右側 {2, 5} の積（10）が一致するため、3 が返されます。もし該当する要素が存在しない配列が渡された場合は、関数は -1 を返します。