Đề bài
Cho mảng n số nguyên chỉ chứa 0 và 1. Tìm số lần đảo bit tối thiểu (đổi 0 thành 1 hoặc ngược lại) để mảng được phân vùng, tức là trước toàn 0, sau toàn 1.
Ví dụ
Nếu arr[] = {1, 0, 0, 1, 1, 1, 0} thì cần 2 lần đảo: đảo 1 đầu tiên và 0 cuối cùng.
Thuật toán
- Nếu quan sát bài toán, sẽ thấy chắc chắn tồn tại một điểm từ 0 đến n-1 mà tất cả phần tử bên trái nên chứa toàn 0 và bên phải toàn 1
- Những chỉ số không tuân theo quy luật này sẽ phải thay đổi. Ý tưởng là đếm tất cả số 0 từ trái sang phải.
Ví dụ mã nguồn
#include <bits/stdc++.h> using namespace std; int getMinToggles(int *arr, int n) { int zeroCnt[n + 1] = {0}; for (int i = 1; i <= n; ++i) { if (arr[i - 1] == 0) { zeroCnt[i] = zeroCnt[i - 1] + 1; } else { zeroCnt[i] = zeroCnt[i - 1]; } } int result = n; for (int i = 1; i <= n; ++i) { result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]); } return result; } int main() { int arr[] = {1, 0, 0, 1, 1, 1, 0}; int n = sizeof(arr) / sizeof(arr[0]); cout << "Minimum toggles = " << getMinToggles(arr, n) << endl; return 0; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum toggles = 2