Việc tìm chỉ số mảng có số lượng số chẵn hoặc lẻ bằng nhau ở hai bên nghĩa là tìm một vị trí mà tại đó, số lượng số chẵn (hoặc số lẻ) ở bên trái bằng với số lượng số chẵn (hoặc số lẻ) ở bên phải.
Dưới đây là một số định nghĩa liên quan:
- Mảng (Array) – Bộ chứa các phần tử cùng kiểu dữ liệu.
- Chỉ số mảng (Array Index) – Vị trí của phần tử trong mảng. Chỉ số luôn bắt đầu từ 0.
- Số chẵn (Even number) – Số chia hết cho 2.
- Số lẻ (Odd number) – Số không chia hết cho 2.
Mọi số nguyên đều là số chẵn hoặc số lẻ.
Ví dụ minh họa
Input: arr[] = {4, 3, 2, 1, 2} Output : 2
Giải thích
Tại chỉ số 2 (giá trị 2), bên trái có 1 số lẻ (3) và bên phải có 1 số lẻ (1).
Bài toán: Cho mảng n số nguyên, tìm chỉ số sao cho số lượng số chẵn bên trái bằng số lượng số chẵn bên phải HOẶC số lượng số lẻ bên trái bằng số lượng số lẻ bên phải. Nếu không tồn tại chỉ số nào thỏa mãn, in -1.
Thuật toán
Để tìm chỉ số thỏa mãn điều kiện, ta đếm số lượng số chẵn/lẻ ở hai bên của từng phần tử.
Bước 1: Với i từ 0 đến n-1, thực hiện các bước 2-5: Bước 2: Khởi tạo e_l, o_l, e_r, o_r = 0. Bước 3: Với j từ 0 đến i-1: đếm e_l (số chẵn) và o_l (số lẻ) bên trái. Bước 4: Với j từ i+1 đến n-1: đếm e_r (số chẵn) và o_r (số lẻ) bên phải. Bước 5: Nếu (e_l == e_r) HOẶC (o_l == o_r) thì in ra i.
Chương trình C++ mẫu
#include <iostream>
using namespace std;
int main() {
int arr[] = {4, 3, 2, 1, 2};
int n = 5;
cout << "Mảng ban đầu: ";
for(int i = 0; i < n; i++) cout << arr[i] << " ";
cout << "\nChỉ số thỏa mãn điều kiện: ";
for (int i = 0; i < n; i++) {
int o_l = 0, e_l = 0;
int o_r = 0, e_r = 0;
for (int j = 0; j < i; j++) {
if (arr[j] % 2 == 0) e_l++;
else o_l++;
}
for (int k = i + 1; k < n; k++) {
if (arr[k] % 2 == 0) e_r++;
else o_r++;
}
if (e_l == e_r || o_l == o_r) cout << i << " ";
}
return 0;
}
Kết quả
Mảng ban đầu: 4 3 2 1 2 Chỉ số thỏa mãn điều kiện: 2