Make Product Equal One
Hazrat Ali
You are given n numbers a1,a2,…,an. With a cost of one coin you can perform the following operation:
Choose one of these numbers and add or subtract 1 from it.
In particular, we can apply this operation to the same number several times.
We want to make the product of all these numbers equal to 1, in other words, we want a1⋅a2 … ⋅an=1.
For example, for n=3 and numbers [1,−3,0] we can make product equal to 1 in 3 coins: add 1 to second element, add 1 to second element again, subtract 1 from third element, so that array becomes [1,−1,−1]. And 1⋅(−1)⋅(−1)=1.
What is the minimum cost we will have to pay to do that?
The first line contains a single integer n (1≤n≤10) — the number of numbers.
The second line contains n integers a1,a2,…,an (−10≤ai≤10) — the numbers.
Output a single number — the minimal number of coins you need to pay to make the product equal to 1.
2 -1 1
2
4 0 0 0 0
4
5 -5 -3 5 3 0
13
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a.begin(), a.end());
long long ans = 0;
for (int i = 0; i < n - 1; i += 2)
{
long long s1 = abs(a[i] + 1) + abs(a[i + 1] + 1);
long long s2 = abs(a[i] - 1) + abs(a[i + 1] - 1);
ans += min(s1, s2);
}
if (n % 2 == 1)
{
ans += abs(a.back() - 1);
}
cout << ans << endl;
return 0;
}