For a given array A of N integers and a sequence S of N integers from the set {−1, 1}, we define val(A, S) as follows:
val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|
(Assume that the sum of zero elements equals zero.)
For a given array A, we are looking for such a sequence S that minimizes val(A,S).
Write a function:
int solution(vector<int> &A);
that, given an array A of N integers, computes the minimum value of val(A,S) from all possible values of val(A,S) for all possible sequences S of N integers from the set {−1, 1}.
For example, given array:
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = -2your function should return 0, since for S = [−1, 1, −1, 1], val(A, S) = 0, which is the minimum possible value.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..20,000];
- each element of array A is an integer within the range [−100..100].
#include <vector>
#include <set>
using namespace std;
int solution(vector<int> &A) {
if (A.size() == 0) return 0;
set<int> sums, tmpSums;
sums.insert(abs(A[0]));
for (auto it = begin(A) + 1; it != end(A); ++it)
{
for (auto s : sums)
{
tmpSums.insert(abs(s + abs(*it)));
tmpSums.insert(abs(s - abs(*it)));
}
sums = tmpSums;
tmpSums.clear();
}
return *sums.begin();
}#include <vector>
#include <set>
using namespace std;
int solution(vector<int> &A) {
if (A.size() == 0) return 0;
set<int> sums, tmpSums;
sums.insert(abs(A[0]));
for (auto it = begin(A) + 1; it != end(A); ++it)
{
for (auto s : sums)
{
tmpSums.insert(abs(s + abs(*it)));
tmpSums.insert(abs(s - abs(*it)));
}
sums = tmpSums;
tmpSums.clear();
}
return *sums.begin();
}#include <vector>
#include <set>
using namespace std;
int solution(vector<int> &A) {
if (A.size() == 0) return 0;
set<int> sums, tmpSums;
sums.insert(abs(A[0]));
for (auto it = begin(A) + 1; it != end(A); ++it)
{
for (auto s : sums)
{
tmpSums.insert(abs(s + abs(*it)));
tmpSums.insert(abs(s - abs(*it)));
}
sums = tmpSums;
tmpSums.clear();
}
return *sums.begin();
}The following issues have been detected: timeout errors.