Số lần lật bit để chuỗi nhị phân xen kẽ C++

Cho chuỗi nhị phân, tìm số lần lật bit tối thiểu để thành chuỗi xen kẽ (0101... hoặc 1010...).

Ví dụ: "10011" → 2 lần lật (thành "10101").

Giải thuật

• Hàm flip(c): trả về '1' nếu c='0', ngược lại '0'
• Hàm getFlipCountToAlternateString(binary, expected): duyệt chuỗi, nếu binary[i]!=expected thì flipCount++; expected=flip(expected)
• Gọi 2 lần với expected='0' và '1', lấy min

Ví dụ minh họa

#include <bits/stdc++.h> 
using namespace std; 

char flip(char binaryDigit) { 
    return binaryDigit == '0' ? '1' : '0'; 
} 

int getFlipCountToAlternateString(string binary, char expected) { 
    int flipCount = 0; 
    for (int i = 0; i < binary.length(); i++) { 
        if (binary[i] != expected) flipCount++; 
        expected = flip(expected); 
    } 
    return flipCount; 
} 

int main() { 
    string binary = "10011"; 
    cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary, '1')) << endl; 
    return 0; 
} 

Đầu ra

2