Code: 63 ()

import sys
sys.path.append('.')
from leet_utils import lc_setup, get_leetcode_problem, lc_export
lc_setup("https://leetcode.com/problems/first-bad-version/", add_cells=False)

Output: 34

✓ Problem loaded: 278. First Bad Version

Note: 10

278. First Bad Version

Note: 27

URL: https://leetcode.com/problems/first-bad-version/
Difficulty: Easy

Code: 45 ()

from IPython.display import HTML
problem = get_leetcode_problem("https://leetcode.com/problems/first-bad-version/")
HTML(problem["content"])

Output: 553

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

1 <= bad <= n <= 2³¹ - 1

Note: 6

Step 1

Note: 318

実装1

アルゴリズムの選択
- [1, 2, ..., n] --(API)--> [False, ..., False, True, ..., True]となる。
- First Trueを見つける方法だが、単調述語なので二分探索（lower_bound, bisect_left）でいける。
実装
- range(1, n + 1)に対し、key=isBadversionで単調述語を作れる。
- 返り値がインデックスであり、1-indexedなversionsより1小さいことに注意。
- すべてのversionがfineなときは分かりやすく-1を返すことにする。（未来の次のバージョンを返すのは違和感がある。）
計算量
- Time: O(log n)
- Extra Space: O(1)

Code: 177 ()

import bisect


# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:


class Solution:
    def firstBadVersion(self, n: int) -> int:
        first_bad_index = bisect.bisect_left(
            range(1, n + 1), True, key=isBadVersion
            )
        first_bad_version = first_bad_index + 1
        if first_bad_version == n + 1:
            # all versions are fine
            return -1
        return first_bad_version

Note: 19

振り返り
- 特にない。

Note: 6

Step 2

Prompt: 24

Step 1のコードをレビューして、改善点を教えてください。

Assistant: 648

🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠

コードを拝見しました。いくつかレビューポイントを挙げますね。

良い点

bisect_left + key の活用はPythonic で簡潔
計算量の分析も正確

改善点・確認事項

問題の制約との整合性
- LeetCodeの問題文では通常「必ず1つ以上のbad versionが存在する」という前提があります。-1を返すケースは実際には発生しない可能性が高いです。問題の制約を確認してみてください。
rangeオブジェクトのインデックスアクセス
- bisect_left(range(1, n+1), ...) は動作しますが、rangeへのインデックスアクセスはO(1)なので問題ありません。ただし、これを知らないと「rangeを全部展開してるのでは？」と誤解されやすいので、コメントがあると親切かも。
より直接的な書き方
- 0-indexedのインデックスを1-indexedのバージョンに変換するのではなく、最初から1-indexedで考える方法もあります：
Copied!
```
def firstBadVersion(self, n: int) -> int:
    return bisect.bisect_left(range(1, n + 1), True, key=isBadVersion) + 1
```
問題の制約で必ずbad versionが存在するなら、この1行で済みます。
手動で二分探索を書く選択肢
- 面接やコーディング練習の観点では、bisectに頼らず自分で二分探索を書く練習も価値があります。この問題はその練習に最適です。

問題の制約を確認してみましょうか？

Note: 343

LLMレビューの感想
- 久しぶりにbisectに頼らず書いてみてもいいかも。
コメント集
- https://discord.com/channels/1084280443945353267/1351704260793995355/1370664386246606899
  - left, right もよく使われるのですが、本当はいい名前ではあまりないです。二分探索をする仕事をシフト制でやるとして、職場に行ってみたら「左が100で右が200」とだけ書いてある業務日誌があったら昨日働いていた人に電話しませんか。「左と右ってどういう意味なのか。」
    - docstringにループ不変条件を書いておくと良いかも

Note: 229

実装2

実装の検討
- bisectを使わずに書く。
- 不変条件の設定の仕方は等号を含めるかどうかで2x2=4パターンあるが、そのうち2つ書いた。
- 1つ目に書いた方は4パターンの中で最もよくみる気がする。
- 2つ目に書いた方は、4パターンの中で最も不人気と思われる。
  - 4パターンの中で唯一 mid = (left + right + 1) // 2 の+1が必要だったりする。

Code: 462 ()

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:


class Solution:
    def firstBadVersion(self, n: int) -> int:
        """Invariant:
        - for all i < left: isBadVersion(i) is False
        - for all i > right: isBadVersion(i) is True
        """
        left = 1
        right = n
        while left <= right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid + 1
        # right == left - 1
        if left == n + 1:
            return -1
        return left


class Solution:
    def firstBadVersion(self, n: int) -> int:
        """Invariant:
        - for all i <= left: isBadVersion(i) is False
        - for all i > right: isBadVersion(i) is True
        """
        left = 0
        right = n
        while left < right:
            mid = (left + right + 1) // 2
            if isBadVersion(mid):
                right = mid - 1
            else:
                left = mid
        # left == right
        if left + 1 == n + 1:
            # all versions are fine
            return -1
        return left + 1

Prompt: 24

Step 2のコードをレビューして、改善点を教えてください。

Assistant: 774

🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠

Step 2のコードを拝見しました！

良い点

不変条件をdocstringに明記しているのが素晴らしい（Discord のコメントを反映してますね）
4パターンのうち2つを意識的に選んで書いている点も学習として良い
ループ終了時の状態（right == left - 1 など）をコメントしているのも◎

改善点・確認事項

2つ目の実装の mid の計算
Copied!
```
mid = (left + right + 1) // 2
```
この +1 が必要な理由をコメントしておくと、後で見返したときに助かります。（left = mid の場合、+1がないと left == right - 1 のとき無限ループになる）
2つ目の実装の終了条件チェック
Copied!
```
if left + 1 == n + 1:
```
これは単に if left == n: と書けますね。
オーバーフロー対策（面接向け）
Copied!
```
mid = left + (right - left) // 2
```
Pythonでは整数オーバーフローがないので不要ですが、C++/Javaなどでは定番の話題です。面接で「他の言語だとどう？」と聞かれることがあります。
不変条件の言葉の統一
- 1つ目: i < left, i > right（開区間的）
- 2つ目: i <= left, i > right（混合）
どちらも正しいですが、不変条件と初期値・更新式・終了条件の整合性を意識して書けているのが伝わります。
細かい点
- 問題の制約上、bad versionは必ず存在するので -1 を返すケースは不要かもしれません（前回と同様）

全体的に、不変条件を意識した丁寧な実装になっていると思います！何か気になる点はありますか？

Note: 99 ()

PR
- https://github.com/huyfififi/coding-challenges/pull/14
- https://github.com/rihib/leetcode/pull/33
- https://github.com/NobukiFukui/Grind75-ProgrammingTraining/pull/25

Prompt: 67

上記に他の人が解いたPRをまとめています。それぞれのPRの代表的なソリューションとレビューコメントをチェックし、PRごとの内容を簡潔にまとめてください。

Assistant: 1,629

🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠

Copied!

{
  "id": "toolu_01UibjijfxcBwKcaP2vapeMJ",
  "call": {
    "function": "read_url",
    "arguments": {
      "url": "https://github.com/huyfififi/coding-challenges/pull/14"
    }
  },
  "result": "'Skip to content\\n\\n## Navigation Menu\\n\\nToggle navigation\\n\\n[ ](/)\\n\\n[ Sign in ](/login?return_t<TRUNCATED>"
}

Copied!

{
  "id": "toolu_016DFeEPnESCYQNNk8j4CVUk",
  "call": {
    "function": "read_url",
    "arguments": {
      "url": "https://github.com/rihib/leetcode/pull/33"
    }
  },
  "result": "'Skip to content\\n\\n## Navigation Menu\\n\\nToggle navigation\\n\\n[ ](/)\\n\\n[ Sign in ](/login?return_t<TRUNCATED>"
}

Copied!

{
  "id": "toolu_01QAKAk7HuG9LXLx6bSbYjxc",
  "call": {
    "function": "read_url",
    "arguments": {
      "url": "https://github.com/NobukiFukui/Grind75-ProgrammingTraining/pull/25"
    }
  },
  "result": "'Skip to content\\n\\n## Navigation Menu\\n\\nToggle navigation\\n\\n[ ](/)\\n\\n[ Sign in ](/login?return_t<TRUNCATED>"
}

各PRの内容をまとめます。

PR 1: huyfififi/coding-challenges#14 (Python)

レビューコメントのポイント:

変数名 left_i について (colorbox): iがindexの略なら省略せずindexと書くか、単にleftにした方が良い
left/rightの意味 (oda): 「左が100で右が200」だけでは意味が分からない。本当は「99以前はgood確認済み、100以降は未確認」という情報を表現したい。変数名を長くするか、ループ不変条件をコメントで明記すべき
オーバーフロー対策: mid = left + (right - left) / 2 の書き方を覚えておくと良い（Pythonでは不要だが他言語で有用）
エッジケース (oda): n=1でwhileに入らないケースへの注意

PR 2: rihib/leetcode#33 (Go)

レビューコメントのポイント:

「半閉区画」→「半開区間」 (nodchip): 用語の訂正
ループ不変条件の説明が不十分 (nodchip): 「rightは常にtrueの範囲に収まる」「leftはtrueに移動する」などの説明に対し、「なぜそうなるのか」「right=midにしてよい理由は？」など根本的な理由を問う質問が多数
isBadVersion()の呼び出し回数 (oda): ループ1回で最大3回呼ばれる実装があり、APIが重い処理の場合に問題になる可能性

特徴: nodchipさんから二分探索の理解を深めるための鋭い質問が多く、ループ不変条件や境界の意味を正確に説明できるかが問われている

PR 3: NobukiFukui/Grind75-ProgrammingTraining#25 (Python)

レビューコメントのポイント:

整数除算 (liquo-rice): int(left + (right - left) / 2) より // を使う方が分かりやすい
colorbox: 「良さそうに見えます」

特徴: シンプルなPRで、軽微なPythonの書き方の指摘のみ

共通して学べるポイント:

変数名とループ不変条件の明示 - left/rightだけでは意味が曖昧なので、不変条件をコメントで書く
APIコールの回数を意識 - isBadVersion()が重い可能性を考慮
Pythonでは // を使う - int(... / 2) より明確

Prompt: 27

各トピックについて、さらに深掘りして詳しく解説してください。

Assistant: 1,395

🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠🧠

では、各トピックを深掘りしていきますね。

1. 変数名とループ不変条件の明示

二分探索の left/right は実は曖昧な名前です。odaさんの指摘が秀逸で：

「左が100で右が200」とだけ書いてある業務日誌があったら昨日働いていた人に電話しませんか

left/right が表しているのは実際には以下のような情報です：

Copied!

# 悪い例：何を意味するか分からない
left = 1
right = n

# 良い例：不変条件を明示
# Invariant:
#   - all versions in [1, left) are good
#   - all versions in (right, n] are bad
left = 1
right = n

不変条件を書くことで：

初期値の妥当性 が確認できる（最初は何も確認していないので、空区間であるべき）
更新式の正しさ が検証できる（不変条件が維持されるか？）
終了条件の意味 が明確になる（何が分かった状態で終わるのか？）

また、区間の表現方法（開/閉）を統一することも重要です：

[left, right]（閉区間）: left <= right で継続、left = mid + 1 or right = mid - 1
[left, right)（半開区間）: left < right で継続、更新式も変わる

2. APIコールの回数を意識

rihib さんのPRで指摘された点です。以下のような実装があったとします：

Copied!

while left < right:
    mid = (left + right) // 2
    if isBadVersion(mid) and not isBadVersion(mid - 1):  # 2回呼ぶ
        return mid
    elif isBadVersion(mid):  # さらに1回
        right = mid
    else:
        left = mid + 1

問題点：

ループ1回で最大3回の isBadVersion() 呼び出し
このAPIがネットワーク越しや重い処理だと性能に影響

改善版：

Copied!

while left < right:
    mid = (left + right) // 2
    if isBadVersion(mid):  # 1回だけ
        right = mid
    else:
        left = mid + 1
return left

一般的な教訓: 外部API・重い関数の呼び出しは最小限に。結果をキャッシュするか、ロジックを工夫する。

3. Pythonでは // を使う

Copied!

# 避けるべき
mid = int(left + (right - left) / 2)

# 推奨
mid = left + (right - left) // 2

理由：

/ は浮動小数点除算、// は整数除算
int() で変換すると、意図が不明瞭になる
浮動小数点の精度問題を避けられる（非常に大きな数の場合）

補足: オーバーフロー対策について

Copied!

# 素朴な書き方（Pythonでは問題なし）
mid = (left + right) // 2

# オーバーフロー対策版
mid = left + (right - left) // 2

Pythonは任意精度整数なのでオーバーフローしませんが、C++/Java/Goなどでは left + right がオーバーフローする可能性があります。面接で「他の言語ではどうする？」と聞かれることがあるので、知っておくと良いです。

何か特定のトピックについてさらに質問はありますか？

Note: 76

他のPRを見た感想。
- 32bit整数などを意識した場合、mid = left + (right - left) // 2と書くと他言語互換っぽくなる。

Note: 6

Step 3

Note: 25

実装3

何も見ずに書き直し

Code: 229 ()

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        """Invariant:
        - all versions in [1, left) are fine
        - all versions in [right, n] are bad
        """
        left = 1
        right = n + 1
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        # left == right
        if right == n + 1:
            return -1
        return right

Note: 187

振り返り
- first Trueを見つけるとき、右側に対する不変条件がi > rightよりi >= rightとなっていた方が、返り値が考えやすいと感じた。
- #実装3は、i < leftとi >= rightに対し不変条件を考えているため返り値がrightと分かりやすい。
- 停止条件もleft == rightと重なるため、分かりやすいと感じる。

Note: 6

Step 4

Note: 18

自分のPR：（自分のPRへのリンク）

Prompt: 46

ここに、私が投稿したStep1-3のPRに対してレビューコメントがついています。それぞれチェックしてまとめてください。

Prompt: 25

それぞれのレビューコメントについて、もう少し詳しく教えてください。

Note: 37

実装4

レビューを受けて書き直し
- （修正点）

Code: 7 ()

class Solution:
    pass

Code: 66 ()

from IPython.display import Markdown

md = lc_export(
    next_url="https://leetcode.com/problems/majority-element/",
    dry_run=True,
    desc="",
    notebook_url=""
)
# Markdown(md)

Output: 49

📁 0278-first-bad-version/0278-first-bad-version.md (19 cells)