Giả sử chúng ta có một mảng A với n phần tử. Trong một thao tác, chúng ta có thể thêm 1 với bất kỳ một phần tử nào được đặt trước trong A. Nếu tổng hoặc tích của tất cả các phần tử trong mảng bằng 0, chúng ta có thể thực hiện thao tác này thêm một lần nữa. Chúng ta phải đếm số bước tối thiểu cần thiết để làm cho cả tổng và tích của tất cả các phần tử trong mảng khác 0?
Vì vậy, nếu đầu vào là A =[-1, 0, 0, 1], thì đầu ra sẽ là 2, bởi vì cả tích và tổng đều bằng 0. Nếu chúng ta thêm 1 vào phần tử thứ hai và thứ ba, mảng sẽ là [−1,1,1,1], tổng sẽ bằng 2 và tích sẽ bằng −1.
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
sum := 0 cnt := 0 n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: x := A[i] sum := sum + x cnt := cnt + (if x is same as 0, then 1, otherwise 0) return (if sum + cnt is same as 0, then cnt + 1, otherwise cnt)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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
{ -1, 0, 0, 1 } Đầu ra
2