On this page

ข้อ 67 · LC338 Counting Bits (นับบิตหนึ่ง) 🟢

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

คืน array (ลิสต์) ของจำนวน bit 1 ในทุกเลขตั้งแต่ 0 ถึง n โดยต่อยอด (DP) จากผลลัพธ์ที่คำนวณไว้แล้ว

โจทย์ (LC338): กำหนดจำนวนเต็ม n ให้ return array (ลิสต์) ชื่อ ans ที่มีความยาว n + 1 โดยที่ ans[i] คือจำนวน bit ที่เป็น 1 ในเลขฐานสองของ i สำหรับทุกค่า 0 <= i <= n

Example 1

Input:: n = 2
Output:: [0, 1, 1]
Explanation:: 0 = 0b0 มี 0 bit, 1 = 0b1 มี 1 bit, 2 = 0b10 มี 1 bit

Example 2

Input:: n = 5
Output:: [0, 1, 1, 2, 1, 2]
Explanation:: 3 = 0b11 มี 2 bit, 4 = 0b100 มี 1 bit, 5 = 0b101 มี 2 bit

Constraints (ข้อจำกัด)

0 <= n <= 10^5
ท้าทาย: ทำให้เสร็จในการกวาดรอบเดียว O(n)

แนวทาง — ต้องใช้อะไร & คิดยังไง

ข้อนี้ใช้แนวคิดแบบ dynamic programming (DP — นำผลลัพธ์เก่ามาต่อยอด) ผสมกับการ shift bit (เลื่อนบิต) เพราะเราต้อง return ทุกเลข 0..n อยู่แล้ว การเก็บคำตอบของเลขเล็กไว้ช่วยเลขใหญ่จึงคุ้มมาก

วิธีง่ายสุดคือ iterate (วน) นับ bit 1 ของแต่ละเลขใหม่ทั้งหมด (เช่นใช้ bin(i).count('1')) ซึ่งได้คำตอบถูกแต่ต้องไล่ดูทุก bit ซ้ำ ๆ ทุกตัว ไม่คุ้มเพราะจริง ๆ แล้ว i กับ i >> 1 (คือ i หารสองปัดลง) มีจำนวน bit 1 เกือบเท่ากัน ต่างแค่ bit ขวาสุดของ i เท่านั้น

initialize (ตั้งค่าเริ่มต้น) array ans ยาว n+1 เติม 0 ไว้ก่อน (ans[0] = 0 ถูกต้องอยู่แล้ว)
iterate i ตั้งแต่ 1 ถึง n
จำนวน bit ของ i = จำนวน bit ของ (i >> 1) ที่คำนวณไว้แล้ว บวกกับ bit ขวาสุดของ i คือ (i & 1)
return ans

จุดพลาดที่พบบ่อย

อย่าลืมเริ่ม loop ที่ 1 ไม่ใช่ 0 เพราะ i >> 1 ตอน i=0 ก็ยังเป็น 0 และ ans[0] ต้องเป็น 0 อยู่แล้ว การเริ่มที่ 1 จึงปลอดภัยกว่า

ไล่ทีละสเต็ป

i	i >> 1	ans[i>>1]	i & 1	ans[i]
1	0	0	1	1
2	1	1	0	1
3	1	1	1	2
4	2	1	0	1
5	2	1	1	2

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def count_bits(n):
    ans = [0] * (n + 1)                 # เตรียมลิสต์ยาว n+1 เติม 0 (ans[0]=0 ถูกแล้ว)
    for i in range(1, n + 1):           # เริ่มที่ 1 เพราะ 0 คำนวณเสร็จแล้ว
        # จำนวนบิตของ i = จำนวนบิตของ (i หารสองปัดลง) บวกบิตขวาสุดของ i
        ans[i] = ans[i >> 1] + (i & 1)  # i>>1 เล็กกว่า i เสมอ จึงมีค่าใน ans แล้ว
    return ans

print(count_bits(2))  # [0, 1, 1]
print(count_bits(5))  # [0, 1, 1, 2, 1, 2]

Output

[0, 1, 1]
[0, 1, 1, 2, 1, 2]

หัวใจคือใช้ผลลัพธ์เก่ามาต่อยอด เมื่อเรา shift bit ของ i ไปขวา 1 ตำแหน่ง (i >> 1) ก็คือตัด bit ขวาสุดทิ้ง เลขที่ได้เล็กกว่า i เสมอจึงคำนวณไว้แล้วใน ans เราแค่หยิบค่านั้นมา แล้วบวก bit ขวาสุดที่เพิ่งตัดออก ซึ่งก็คือ i & 1 (0 หรือ 1)

ถ้าเปลี่ยนไปนับ bit ของแต่ละตัวใหม่ทั้งหมดก็ได้คำตอบเหมือนกัน แต่ต้อง iterate ดูทุก bit ซ้ำ ๆ ทำให้ช้าลง วิธีต่อยอดนี้จึงเร็วกว่าเพราะแต่ละตัวใช้แค่การหยิบค่าเก่ามาบวกอีกครั้งเดียว

Time O(n) คำนวณแต่ละตัวในเวลาคงที่ ตัวละครั้ง · Space O(n) เก็บ array คำตอบ n+1 ช่อง (ถ้าไม่นับ array ผลลัพธ์ก็ถือว่า O(1))

💡 สรุป pattern

โจทย์นับ/สร้างค่าเป็นชุด 0..n มักต่อยอดจากค่าที่เล็กกว่าได้ ลองมองว่าค่าใหม่ต่อจากค่าเก่าตัวไหน (ที่นี่คือ i >> 1) แล้วบวกส่วนต่างเข้าไป — คือแนวคิด DP บน bit