Pythonで指定した区間内の奇数の個数を数えるプログラム

2つの非負整数 left と right が与えられたとき、この2つの値の間（両端を含む）に存在する奇数がいくつあるかを求める問題を考えてみましょう。

例えば、left = 3、right = 15 が入力された場合、出力は 7 になります。これは、この範囲に含まれる奇数が [3, 5, 7, 9, 11, 13, 15] の7個だからです。

解法のアプローチ

この問題は、範囲内のすべての数を1つずつ確認しなくても、数学的な性質を利用すれば定数時間（O(1)）で解くことができます。手順は以下の通りです。

• left または right のどちらか一方でも奇数である場合：
  (right - left) // 2 + 1 を返す
• どちらも偶数である場合：
  (right - left) // 2 を返す

このロジックが成り立つ理由は、連続する整数の中には必ず偶数と奇数が交互に現れるためです。範囲の幅 right - left に対して半分ずつ偶数・奇数が含まれ、端点のどちらかが奇数であれば奇数が1つ多くなる、という仕組みです。

Pythonでの実装例

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

def solve(left, right):
    if left % 2 == 1 or right % 2 == 1:
        return (right - left) // 2 + 1
    else:
        return (right - left) // 2

left = 3
right = 15
print(solve(left, right))

入力

3, 15

出力

7

補足：別のシンプルな書き方

より直感的に理解しやすい方法として、(left + 1) // 2 と (right + 1) // 2 の差を利用する手法もあります。

def solve(left, right):
    return (right + 1) // 2 - left // 2

この式は「0からrightまでの奇数の個数」から「0からleft-1までの奇数の個数」を引くことで、目的の範囲内の奇数の個数を求めています。条件分岐が不要になるため、コードがより簡潔になります。

どちらの方法でも計算量はO(1)であり、範囲が非常に大きい場合でも高速に動作します。ループで全要素を走査するO(n)のアプローチと比べて、大幅に効率的です。