Pythonで配列の全要素をちょうどk回の操作でゼロにできるかどうかを判定する方法

配列 nums と整数 k が与えられたとき、次の操作をちょうど k 回実行することで、nums のすべての要素を 0 にできるかどうかを判定する問題を考えます。

• 操作: nums 内の最小値を、nums のすべての非ゼロ要素から引く。

例えば、入力が nums = [2, 2, 3, 5]、k = 3 の場合、出力は True になります。まず 2 を引いて配列は [0, 0, 1, 3] となり、次に 1 を引いて [0, 0, 0, 2]、さらに 2 を引けば [0, 0, 0, 0] となります。つまり、ちょうど 3 回の操作ですべての要素が 0 になったためです。

解法のアプローチ

この操作では、1 回ごとに「その時点での最小値」を持つ要素がすべて 0 になります。言い換えると、操作を 1 回実行するたびに、配列内の異なる値が 1 種類ずつ消えていくことになります。

したがって、すべての要素を 0 にするのに必要な操作回数は、配列内のユニークな要素(異なる値)の数と一致します。よって、以下の手順で判定できます。

• 配列内の異なる要素の数がちょうど k 個であれば、True を返す。
• それ以外の場合は、False を返す。

それでは、実際の実装を見てみましょう。

サンプルコード

def solve(nums, k):
    distinct = set(nums)

    if len(distinct) == k:
        return True
    return False

nums = [2, 2, 3, 4]
k = 3
print(solve(nums, k))

入力

[2, 2, 3, 4], 3

出力

True

この例では、配列 [2, 2, 3, 4] のユニークな要素は {2, 3, 4} の 3 種類であり、k = 3 と一致するため、結果は True となります。set を使うことで重複を簡単に除去でき、計算量も O(n) と非常に効率的です。