Pythonで3つ連続した奇数が存在するかどうかを判定するプログラム

nums という整数型の配列が与えられたとき、その中に「3つ連続した奇数」が存在するかどうかを判定するプログラムを作成します。

たとえば、入力が nums = [18,15,2,19,3,11,17,25,20] の場合、[3, 11, 17] という3つの連続した奇数が含まれているため、出力は True になります。

解決のためのアプローチ

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

• length := 配列 nums の要素数とします。

• length が 1 または 2 の場合は、3つ連続した奇数が存在し得ないため False を返します。

• それ以外の場合は、i を 0 から「要素数 − 3」まで順に走査します。

  • nums[i]、nums[i+1]、nums[i+2] がすべて奇数であれば、True を返します。

• 最後まで走査しても見つからなければ、False を返します。

Pythonでの実装例

以下の実装例を見て、処理の流れを確認してみましょう。

def solve(nums):
    length = len(nums)
    if length == 1 or length == 2:
        return False
    else:
        for i in range(len(nums) - 2):
            if nums[i] % 2 != 0 and nums[i+1] % 2 != 0 and nums[i+2] % 2 != 0:
                return True
        return False

nums = [18,15,2,19,3,11,17,25,20]
print(solve(nums))

入力

[18,15,2,19,3,11,17,25,20]

出力

True

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。非常にシンプルで効率的な方法です。なお、奇数の判定には剰余演算子 % を使って「2で割った余りが0でないか」を確認しています。負の数が含まれる場合でも Python では正しく動作することに注意してください。