Giả sử chúng ta có một mảng A với n phần tử. Chúng ta phải tìm độ dài của tập con không rỗng của các phần tử của nó sao cho tổng của chúng là chẵn hoặc trả về -1 khi không có tập con như vậy.
Ví dụ, nếu đầu vào là A = [1, 3, 7], thì đầu ra sẽ là 2, vì tổng của [1, 3] là 4.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
n := kích thước của A for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: if A[i] mod 2 giống 0, thì: k := i + 1 if n là 1 VÀ k là 0, thì: return -1 ngược lại khi k khác 0, thì: return 1 Ngược lại return 2
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A) { long n = A.size(), k = 0; for (long i = 0; i < n; i++) { if (A[i] % 2 == 0) { k = i + 1; } } if (n == 1 & k == 0) { return -1; } else if (k != 0) { return 1; } else { return 2; } } int main() { vector<int> A = { 1, 3, 7 }; cout << solve(A) << endl; }Đầu vào
{ 1, 3, 7 }Đầu ra
2