Pythonで配列の全要素を等しくするために必要な操作回数の求め方

ある要素の配列が与えられ、各ステップで n - 1 個の要素を1ずつ増やすことが許されているとします。このとき、配列の全要素を等しくするまでに必要な操作の総回数を求めるのが目標です。

例えば、リスト [1, 2, 3] の場合、すべての要素を等しくするには3回の操作が必要になります。この問題に対する基本的な解法の一つは、各ステップで最大値を見つけ、それ以外の要素を1ずつ増やしていくというものです。実際にコードを書いてみましょう。

方法1：シミュレーションによる解法

def main():
    # 配列の初期化
    arr = [1, 2, 3]
    # 操作回数を0で初期化
    no_of_operations = 0
    flag = 0
    # 全要素が等しくなるまで操作を繰り返す
    while not are_equal(arr):
        flag = 1
        # リストから最大値を見つける
        maximum = max(arr)
        # 最大値以外の要素を1ずつ増やす
        for i in range(len(arr)):
            if arr[i] != maximum:
                arr[i] += 1
        # 操作回数を1増やす
        no_of_operations += 1
    print(no_of_operations) if flag == 0 else print(no_of_operations + 1)

# すべての要素が等しいかどうかを判定する関数
def are_equal(arr):
    global no_of_operations
    for i in range(len(arr) - 1):
        if arr[i] != arr[i + 1]:
            return False
    return True

if __name__ == '__main__':
    main()

出力

上記のプログラムを実行すると、次の結果が得られます。

3

方法2：合計値と最小値を使った効率的な解法

上記のシミュレーション方式は直感的に分かりやすい反面、配列のサイズが大きくなると計算に非常に時間がかかります。そこで活躍するのが、配列の合計値と最小値を使った数学的なアプローチです。手順は以下の通りです。

• 配列の合計値を求める。
• 配列内の最小値を求める。
• 「sum - (length × smallest)」という式で計算した値を出力する。

この式により、ループで操作を繰り返すことなく、必要な操作回数を一度の計算で導き出せます。

例：数式による解法のコード

# 配列の初期化
arr = [1, 2, 3]
# 配列の長さ
length = len(arr)
# 配列の要素の合計
elements_sum = sum(arr)
# 全要素の中で最も小さい値
smallest = min(arr)
# 操作回数を計算して出力
print(elements_sum - (length * smallest))

出力

上記のコードを実行すると、次の結果が得られます。

3

まとめ

今回紹介した2つの方法のうち、合計値と最小値を使う方法（方法2）は、シミュレーション方式（方法1）よりもコードがシンプルで、処理速度も大幅に速いため、大規模なデータにも対応できます。まずは方法1でアルゴリズムの動きを理解し、その後、方法2のような数学的な最適化を学ぶことで、効率的なプログラミングの考え方が身につきます。本チュートリアルについてご不明な点があれば、ぜひコメント欄でお知らせください。