Cho mảng A kích thước n. Mỗi phép: tăng một phần tử lên 1. Nếu tổng hoặc tích mảng bằng 0, phải làm thêm phép. Tìm số phép tối thiểu để tổng và tích đều khác 0.
Ví dụ
Với A=[-1,0,0,1], đầu ra 2. Tăng 2 số 0 thành 1 → mảng [-1,1,1,1], tổng=2, tích=-1.
Giải thuật
Đếm cnt = số phần tử 0. Tính sum = tổng mảng. Cần tăng các số 0 lên 1 (tốn cnt phép). Sau đó tổng mới = sum + cnt. Nếu sum + cnt == 0 thì cần thêm 1 phép. Kết quả: sum+cnt==0 ? cnt+1 : cnt.
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A) {
int sum = 0, cnt = 0;
int n = A.size();
for (int i = 0; i < n; i++) {
int x = A[i];
sum += x;
cnt += (x == 0 ? 1 : 0);
}
return (sum + cnt == 0) ? cnt + 1 : cnt;
}
int main() {
vector<int> A = { -1, 0, 0, 1 };
cout << solve(A) << endl;
}
Đầu vào / Đầu ra
Input: { -1, 0, 0, 1 }
Output: 2