刷題理解筆記

題目編號：LeetCode 1018

題目名稱：Binary Prefix Divisible by 5

題目連結

題目描述

給定一個二進位陣列 nums（0-indexed）。

我們定義 x_i 為前綴 nums[0..i] 的二進位表示所對應的十進位數字。

舉例說明：

• 如果 nums = [1,0,1]
• x0 = 1 (二進位 1 → 十進位 1)
• x1 = 2 (二進位 10 → 十進位 2)
• x2 = 5 (二進位 101 → 十進位 5)

任務：回傳一個布林陣列 answer，其中 answer[i] = True 如果 x_i 可被 5 整除，否則為 False。

範例 1

輸入: nums = [0,1,1]
輸出: [True, False, False]
解析:
- 前綴二進位: 0, 01, 011
- 對應十進位: 0, 1, 3
- 只有 0 可以被 5 整除 → True

範例 2

輸入: nums = [1,1,1]
輸出: [False, False, False]
解析:
- 前綴二進位: 1, 11, 111
- 對應十進位: 1, 3, 7
- 全部都不能被 5 整除 → [False, False, False]

限制條件

• 1 <= nums.length <= 10^5
• nums[i] ∈ {0, 1}

核心概念 / 思路

1. 二進位累積公式：
   python value = value * 2 + bit
2. 模運算 %5 防止數字過大
3. 0 也可以被 5 整除
4. 過程中累積的 value 代表十進位的數量概念

例子解析

範例程式碼

from typing import List

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        result = []
        cur = 0
        for bit in nums:
            cur = (cur * 2 + bit) % 5
            result.append(cur == 0)
        return result

小結 / 提醒

• 二進位累積公式：value = value * 2 + bit
• 模運算 %5 可避免數字爆掉
• 0 也算可以被整除
• 所有進位制都可用公式 value = value * base + digit 進行累積