โปรแกรม C++ นับขั้นตอนน้อยที่สุดทำให้ผลรวมและผลคูณไม่เป็นศูนย์

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A n องค์ประกอบ ใน 1 ขั้นตอน สามารถบวก 1 เข้ากับองค์ประกอบใดก็ได้ ถ้าผลรวมหรือผลคูณของทุกองค์ประกอบเท่ากับ 0 สามารถทำขั้นตอนเพิ่มได้ ต้องการนับขั้นตอนน้อยที่สุดทำให้ทั้งผลรวมและผลคูณต่างจาก 0

ตัวอย่าง: A = [-1, 0, 0, 1] ผลลัพธ์คือ 2 เพราะผลรวมและผลคูณเป็น 0 บวก 1 เข้าตัวที่ 2 และ 3 ได้ [-1, 1, 1, 1] ผลรวม 2 ผลคูณ -1

ขั้นตอนการแก้ปัญหา

sum := 0, cnt := 0
n := ขนาดของ A
สำหรับ i := 0 ถึง n-1:
    x := A[i]
    sum := sum + x
    cnt := cnt + (ถ้า x == 0 แล้ว 1 มิฉะนั้น 0)
คืนค่า (ถ้า sum + cnt == 0 แล้ว cnt + 1 มิฉะนั้น cnt)

ตัวอย่างโค้ด 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;
}

อินพุต

{ -1, 0, 0, 1 }

เอาต์พุต

2