โจทย์: กำหนดตัวเลขไม่ติดลบ n หาความยาวของลำดับ 1 ติดกัน (Consecutive 1s) ที่ยาวที่สุดในรูปแบบไบนารีของ n
ตัวอย่าง
Input: n = 1469
Output: 4
เหตุผล: 1469 ในไบนารี = 10110111101 มีลำดับ 1 ติดกันยาวสุด 4 ตัว (1111)
อัลกอริทึม: Bit Manipulation Trick
ใช้คุณสมบัติ: n & (n << 1) จะกำจัด 1 ตัวสุดท้ายของแต่ละลำดับ 1 ติดกัน ทำซ้ำจน n == 0 จำนวนรอบ = ความยาวลำดับ 1 ติดกันยาวสุด
หลักการทำงาน
n = 1469 = 10110111101₂ Round 1: n & (n << 1) 10110111101 & 01101111010 (<< 1) = 00100111000 → นับ 1 Round 2: n & (n << 1) 00100111000 & 01001110000 = 00000110000 → นับ 2 Round 3: n & (n << 1) 00000110000 & 00001100000 = 00000100000 → นับ 3 Round 4: n & (n << 1) 00000100000 & 00001000000 = 00000000000 → นับ 4, n=0 หยุด
โค้ด Python
def solve(n):
count = 0
while n != 0:
n = n & (n << 1)
count += 1
return count
# ทดสอบ
n = 1469
print(solve(n)) # Output: 4ความซับซ้อน
- Time Complexity: O(k) โดย k = ความยาวลำดับ 1 ติดกันยาวสุด (สูงสุด log₂ n)
- Space Complexity: O(1)
วิธีอื่น (String-based)
def solve_string(n):
binary = bin(n)[2:] # ตัด '0b' ออก
return max(len(s) for s in binary.split('0'))
print(solve_string(1469)) # 4การทดสอบเพิ่มเติม
print(solve(0)) # 0 (ไบนารี: 0)
print(solve(1)) # 1 (ไบนารี: 1)
print(solve(3)) # 2 (ไบนารี: 11)
print(solve(7)) # 3 (ไบนารี: 111)
print(solve(15)) # 4 (ไบนารี: 1111)
print(solve(1469)) # 4 (ไบนารี: 10110111101)
print(solve(2**20-1)) # 20 (ทั้งหมดเป็น 1)การประยุกต์ใช้
- Bit manipulation tricks
- การวิเคราะห์รูปแบบบิต
- โจทย์แข่งขันเขียนโปรแกรม (Competitive Programming)
