Binary Prefix Divisible By 5 ใน Python

โจทย์: ให้ Array A ของ 0 และ 1 ให้ N[i] คือค่าบाइनนารีของ Subarray A[0] ถึง A[i] หา List ของ Boolean ว่า N[i] หาร 5 ลงตัวหรือไม่

Input/Output

Input:  [0, 1, 1, 1, 1, 1]
Output: [True, False, False, False, True, False]

อัลกอริทึม

1. แปลง Array ทั้งหมดเป็นตัวเลข Binary หนึ่งตัว
2. วนลูปจาก MSB ไป LSB (ขวาไปซ้าย)
3. เช็คหาร 5 ลงตัว บันทึกผล
4. Shift right 1 bit (หาร 2) สำหรับรอบถัดไป

ตัวอย่างโค้ด (LeetCode Style)

class Solution:
    def prefixesDivBy5(self, A):
        length = len(A)
        ans = [False] * length
        number = int("".join(map(str, A)), 2)
        
        for i in range(length):
            if number % 5 == 0:
                ans[length - i - 1] = True
            number = number >> 1
        
        return ans

ob = Solution()
print(ob.prefixesDivBy5([0, 1, 1, 1, 1, 1]))

ผลลัพธ์

[True, False, False, False, True, False]

การปรับปรุงประสิทธิภาพ (O(N) Time, O(1) Space): คำนวณ Modulo แบบ Incremental ไม่ต้องแปลงทั้ง Array

def prefixesDivBy5(self, A):
    ans = []
    num = 0
    for bit in A:
        num = ((num << 1) | bit) % 5
        ans.append(num == 0)
    return ans

วิธีนี้เร็วกว่าและไม่มีปัญหา Integer Overflow สำหรับ Array ใหญ่