Tìm số d sao cho sau chia mảng có đủ số dương bằng C++

Mô tả bài toán

Cho mảng A n phần tử. Tìm d ≠ 0 sao cho sau khi chia mỗi phần tử cho d, số phần tử dương ≥ ceil(n/2). Nếu nhiều d thỏa mãn, trả về bất kỳ.

Ví dụ

A = [10, 0, -7, 2, 6], n=5 → cần ≥3 số dương. d=4 cho [2.5, 0, -1.75, 0.5, 1.5] → 3 số dương. Output: 4 (hoặc 1, -1, 0 tùy logic).

Thuật toán

Đếm số dương (z) và số âm (f) trong mảng gốc. Nếu 2*z ≥ n thì d=1 (giữ nguyên dấu). Nếu 2*f ≥ n thì d=-1 (đảo dấu). Ngược lại d=0 (không thể).

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int z = 0, f = 0;
    int n = A.size();
    for (int a : A) {
        if (a > 0) z++;
        if (a < 0) f++;
    }
    if (2*z >= n) return 1;
    else if (2*f >= n) return -1;
    else return 0;
}

int main() {
    vector<int> A = {10, 0, -7, 2, 6};
    cout << solve(A) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {10, 0, -7, 2, 6}

Output: 1