Pythonで配列の末尾に到達するのに数値Kが十分かどうかを判定する方法

配列 nums と整数 k が与えられたとき、特定の操作を繰り返しながら配列の末尾まで到達できるかどうかを判定する問題を考えてみましょう。

操作のルール

配列を先頭から順に走査し、以下のルールに従って処理を進めます。

• 現在の要素が素数でない場合: k の値を 1 減らします
• 現在の要素が素数の場合: k の値を初期値に戻します

具体例

例として、nums = [8, 5, 6, 7, 8]、k = 2 の場合の出力は True になります。処理の流れは以下の通りです。

• nums[0] = 8 は素数ではないため、k = 1 になります
• nums[1] = 5 は素数なので、k は初期値の 2 に戻ります
• nums[2] = 6 は素数ではないため、k = 1 になります
• nums[3] = 7 は素数なので、k は再び 2 に戻ります
• nums[4] = 8 は素数ではないため、k = 1 になりますが、この時点で最後のインデックスに到達しています

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 変数 temp に k の初期値を保存しておきます
• 配列の各要素に対して以下を繰り返します
  • 要素が素数であれば、k を temp(初期値)にリセットします
  • そうでなければ、k を 1 減らします
• k が 0 以下になり、かつ現在位置が最後のインデックスより前で、次の要素も素数でない場合は False を返します
• ループが最後まで完了すれば True を返します

サンプルコード

以下が実際のPythonでの実装例です。

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(arr, k):
    temp = k
    for i in range(len(arr)):
        if isPrime(arr[i]):
            k = temp
        else:
            k -= 1
        
        if k <= 0 and i < (len(arr) - 1) and isPrime(arr[i + 1]) == False:
            return False
            
    return True

nums = [8, 5, 6, 7, 8]
k = 2
print(solve(nums, k))

入力

[8, 5, 6, 7, 8], 2

出力

True

計算量について

上記の isPrime 関数は単純な試し割り法を使用しているため、各要素の素数判定に O(n) の時間がかかり、全体の計算量は O(n²) となります。大きな配列を扱う場合は、平方根までの割り算に限定したり、エラトステネスの篩を活用することで効率化できます。