【Python】1と2のみを含む配列を合計が等しい2つの部分に分割できるか判定する方法

問題概要

1と2だけが格納された配列 nums が与えられます。この配列を、各部分の要素の合計が等しくなるように2つの部分へ分割できるかどうかを判定しましょう。

例えば、入力が nums = [1, 1, 2, 2, 2] の場合、[1, 1, 2] と [2, 2] のように分割できます。それぞれの合計は4で等しいため、出力は True となります。

解法のアプローチ

この問題は、配列全体の合計と「1」の個数に着目することで、線形時間で効率的に解けます。手順は以下の通りです。

• 配列全体の合計 total を求めます。
• total が奇数の場合、2つの部分で同じ合計にすることは不可能なので False を返します。
• 目標値は合計の半分 total // 2 です。この値が偶数であれば、「2」だけで目標値を構成できるため True を返します。
• 目標値が奇数の場合、その部分には少なくとも1つの「1」が必要になります。したがって、配列に「1」が1つでも存在すれば True、存在しなければ False を返します。

実装例

以下のコードで、このロジックを確認してみましょう。

def solve(nums):
    total = sum(nums)
    one_count = nums.count(1)

    # 合計が奇数なら均等分割は不可能
    if total % 2:
        return False

    # 目標値(total // 2)が偶数なら、2だけで構成できる
    if (total // 2) % 2 == 0:
        return True

    # 目標値が奇数の場合は、その部分に「1」が必要
    if one_count > 0:
        return True
    else:
        return False

nums = [1, 1, 2, 2, 2]
print(solve(nums))

入力

[1, 1, 2, 2, 2]

出力

True

計算量の評価

時間計算量: O(n) — 合計と「1」の個数を求めるために配列を一度ずつ走査します。
空間計算量: O(1) — 追加のデータ構造は不要で、定数個の変数のみを使用します。

まとめ

この問題のポイントは、全要素が1か2に限定されている点です。合計の偶奇と半分の値の偶奇、そして「1」の有無という3つの条件を組み合わせることで、実際に分割を試みることなく即座に答えを導き出せます。