โจทย์
มี Binary String s สามารถ Flip บิตได้ (0↔1) ต้องการให้ String เป็น Alternating (ไม่มีบิตติดกันเหมือนกัน) หาจำนวนครั้งน้อยที่สุดที่ต้อง Flip
ตัวอย่าง: s = "11100011" → Output: 3 (Flip ตำแหน่ง 1, 4, 7 ได้ "10101010")
อัลกอริธึม
- นับจำนวน 0 และ 1 ในตำแหน่งคู่ (Even) และคี่ (Odd)
- มี 2 รูปแบบ Alternating: เริ่ม 0 หรือ เริ่ม 1
- คำนวณการ Flip ที่ต้องทำแต่ละรูปแบบ เลือกค่าน้อยที่สุด
โค้ด Python
def solve(s):
change = 0
even_1 = even_0 = 0
odd_1 = odd_0 = 0
for i in range(len(s)):
if i % 2 == 0:
if s[i] == '1': even_1 += 1
else: even_0 += 1
else:
if s[i] == '1': odd_1 += 1
else: odd_0 += 1
# รูปแบบ 1: เริ่ม 1 (Even=1, Odd=0) -> flip even_0 + odd_1
# รูปแบบ 2: เริ่ม 0 (Even=0, Odd=1) -> flip even_1 + odd_0
if (even_1 + odd_0) > (even_0 + odd_1):
change = even_0 + odd_1
else:
change = even_1 + odd_0
return change
s = "11100011"
print(solve(s)) # Output: 3
Input / Output
Input: "11100011"
Output: 3
