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(int A[], int N);
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].
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
typedef struct _res{
int odd;
int even;
}stres;
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
switch(N){
case 0:
return 0;
case 1:
return abs(A[0]);
case 2:
{
int sp=abs(abs(A[0])+abs(A[1]));
int sm=abs(abs(A[0])-abs(A[1]));
return (sp<sm)?sp:sm;
}
}
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
sum+=val;
A[i]=val;
}
stres * result=calloc(sum+1,sizeof(stres));
result[abs(A[0]+A[1])].even=1;
result[abs(A[0]-A[1])].even=1;
int pol=0;
int subsum=sum-A[0]-A[1];
//printf("subsum=%d-%d-%d=%d\n",sum,A[0],A[1],subsum);
for(int i=2;i<N;i++){
pol=i%2;
for(int j=0;j<subsum+1;j++){
if((result[j].odd!=i-1)&&(result[j].even!=i-1)) continue;
if(pol){
result[abs(j+A[i])].even=i;
result[abs(j-A[i])].even=i;
}
else{
result[abs(j+A[i])].odd=i;
result[abs(j-A[i])].odd=i;
}
//printf("+result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
}
subsum-=A[i];
//printf("subsum=%d\n",subsum);
}
for(int i=0;i<sum+1;i++){
//printf("result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
if((result[i].odd==N-1)||(result[i].even==N-1)) return i;
}
return 0;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
typedef struct _res{
int odd;
int even;
}stres;
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
switch(N){
case 0:
return 0;
case 1:
return abs(A[0]);
case 2:
{
int sp=abs(abs(A[0])+abs(A[1]));
int sm=abs(abs(A[0])-abs(A[1]));
return (sp<sm)?sp:sm;
}
}
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
sum+=val;
A[i]=val;
}
stres * result=calloc(sum+1,sizeof(stres));
result[abs(A[0]+A[1])].even=1;
result[abs(A[0]-A[1])].even=1;
int pol=0;
int subsum=sum;
//printf("subsum=%d-%d-%d=%d\n",sum,A[0],A[1],subsum);
for(int i=2;i<N;i++){
pol=i%2;
for(int j=0;j<subsum+1;j++){
if((result[j].odd!=i-1)&&(result[j].even!=i-1)) continue;
if(pol){
result[abs(j+A[i])].even=i;
result[abs(j-A[i])].even=i;
}
else{
result[abs(j+A[i])].odd=i;
result[abs(j-A[i])].odd=i;
}
//printf("+result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
}
subsum-=A[i];
//printf("subsum=%d\n",subsum);
}
for(int i=0;i<sum+1;i++){
//printf("result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
if((result[i].odd==N-1)||(result[i].even==N-1)) return i;
}
return 0;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
typedef struct _res{
int odd;
int even;
}stres;
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
switch(N){
case 0:
return 0;
case 1:
return abs(A[0]);
case 2:
{
int sp=abs(abs(A[0])+abs(A[1]));
int sm=abs(abs(A[0])-abs(A[1]));
return (sp<sm)?sp:sm;
}
}
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
sum+=val;
A[i]=val;
}
stres * result=calloc(sum+1,sizeof(stres));
result[abs(A[0]+A[1])].even=1;
result[abs(A[0]-A[1])].even=1;
int pol=0;
int subsum=sum;
//printf("subsum=%d-%d-%d=%d\n",sum,A[0],A[1],subsum);
for(int i=2;i<N;i++){
pol=i%2;
for(int j=0;j<subsum+1;j++){
if((result[j].odd!=i-1)&&(result[j].even!=i-1)) continue;
if(pol){
result[abs(j+A[i])].even=i;
result[abs(j-A[i])].even=i;
}
else{
result[abs(j+A[i])].odd=i;
result[abs(j-A[i])].odd=i;
}
//printf("+result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
}
//subsum-=A[i];
//printf("subsum=%d\n",subsum);
}
for(int i=0;i<sum+1;i++){
//printf("result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
if((result[i].odd==N-1)||(result[i].even==N-1)) return i;
}
return 0;
}
[2, 4, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
typedef struct _res{
int odd;
int even;
}stres;
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
switch(N){
case 0:
return 0;
case 1:
return abs(A[0]);
case 2:
{
int sp=abs(abs(A[0])+abs(A[1]));
int sm=abs(abs(A[0])-abs(A[1]));
return (sp<sm)?sp:sm;
}
}
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
sum+=val;
A[i]=val;
}
stres * result=calloc(sum+1,sizeof(stres));
result[abs(A[0]+A[1])].even=1;
result[abs(A[0]-A[1])].even=1;
int pol=0;
int subsum=sum;
//printf("subsum=%d-%d-%d=%d\n",sum,A[0],A[1],subsum);
for(int i=2;i<N;i++){
pol=i%2;
for(int j=0;j<subsum+1;j++){
if((result[j].odd!=i-1)&&(result[j].even!=i-1)) continue;
if(pol){
result[abs(j+A[i])].even=i;
result[abs(j-A[i])].even=i;
}
else{
result[abs(j+A[i])].odd=i;
result[abs(j-A[i])].odd=i;
}
//printf("+result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
}
//subsum-=A[i];
//printf("subsum=%d\n",subsum);
}
for(int i=0;i<sum+1;i++){
//printf("result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
if((result[i].odd==N-1)||(result[i].even==N-1)) return i;
}
return 0;
}
[2, 4, 1]
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
typedef struct _res{
int odd;
int even;
}stres;
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
switch(N){
case 0:
return 0;
case 1:
return abs(A[0]);
case 2:
{
int sp=abs(abs(A[0])+abs(A[1]));
int sm=abs(abs(A[0])-abs(A[1]));
return (sp<sm)?sp:sm;
}
}
int sum=0;
for(int i=0;i<N;i++){
int val=abs(A[i]);
sum+=val;
A[i]=val;
}
stres * result=calloc(sum+1,sizeof(stres));
result[abs(A[0]+A[1])].even=1;
result[abs(A[0]-A[1])].even=1;
int pol=0;
int subsum=sum;
//printf("subsum=%d-%d-%d=%d\n",sum,A[0],A[1],subsum);
for(int i=2;i<N;i++){
pol=i%2;
for(int j=0;j<subsum+1;j++){
if((result[j].odd!=i-1)&&(result[j].even!=i-1)) continue;
if(pol){
result[abs(j+A[i])].even=i;
result[abs(j-A[i])].even=i;
}
else{
result[abs(j+A[i])].odd=i;
result[abs(j-A[i])].odd=i;
}
//printf("+result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
}
//subsum-=A[i];
//printf("subsum=%d\n",subsum);
}
for(int i=0;i<sum+1;i++){
//printf("result[%d]=%d,%d\n",i,result[i].odd,result[i].even);
if((result[i].odd==N-1)||(result[i].even==N-1)) return i;
}
return 0;
}
The following issues have been detected: timeout errors.