Tasks Details
hard
1.
MinAbsSum
Given array of integers, find the lowest absolute sum of elements.
Task Score
100%
Correctness
Not assessed
Performance
Not assessed
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].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C
Time spent on task 13 minutes
Notes
not defined yet
Task timeline
Code: 14:40:07 UTC,
c,
verify,
result: Failed
int abs(int x)
{
return (x < 0) ? -x : x;
}
int min_abs_sum ( int A[], int n )
{
int *count = (int*)calloc(105, sizeof(int);
int i;
for (i = 0; i < n; i++)
count[A[i]]++;
int suma = 0;
for (i = 100; i >= 0; i--)
while (count[i]-- > 0)
suma = abs(suma-i);
return suma;
}
Analysis
Compile error
In file included from /tmp/chk_R0tg2dir/user.c:17: /tmp/chk_R0tg2dir/func.c: In function 'min_abs_sum': /tmp/chk_R0tg2dir/func.c:9: error: expected ')' before ';' token /tmp/chk_R0tg2dir/func.c:23: error: expected ',' or ';' before '}' token /tmp/chk_R0tg2dir/user.c:20: error: 'n' redeclared as different kind of symbol /tmp/chk_R0tg2dir/func.c:7: note: previous definition of 'n' was here /tmp/chk_R0tg2dir/user.c:70: warning: 'main' is normally a non-static function /tmp/chk_R0tg2dir/user.c:95: error: expected declaration or statement at end of input /tmp/chk_R0tg2dir/func.c:9: warning: unused variable 'count'
Code: 14:40:17 UTC,
c,
verify,
result: Failed
int abs(int x)
{
return (x < 0) ? -x : x;
}
int min_abs_sum ( int A[], int n )
{
int *count = (int*)calloc(105, sizeof(int));
int i;
for (i = 0; i < n; i++)
count[A[i]]++;
int suma = 0;
for (i = 100; i >= 0; i--)
while (count[i]-- > 0)
suma = abs(suma-i);
return suma;
}
Analysis
expand all
Example tests
1.
0.001 s
WRONG ANSWER,
got 2 expected 0
Code: 14:41:17 UTC,
c,
verify,
result: Passed
int abs(int x)
{
return (x < 0) ? -x : x;
}
int min_abs_sum ( int A[], int n )
{
int *count = (int*)calloc(105, sizeof(int));
int i;
for (i = 0; i < n; i++)
count[abs(A[i])]++;
int suma = 0;
for (i = 100; i >= 0; i--)
while (count[i]-- > 0)
suma = abs(suma-i);
return suma;
}
Analysis
Code: 14:46:22 UTC,
c,
verify,
result: Passed
int abs(int x)
{
return (x < 0) ? -x : x;
}
int min_abs_sum ( int A[], int n )
{
int *count = (int*)calloc(105, sizeof(int));
int i;
for (i = 0; i < n; i++)
count[abs(A[i])]++;
int suma = 0;
for (i = 100; i >= 0; i--)
while (count[i]-- > 0)
suma = abs(suma-i);
return suma;
}
Analysis
Code: 14:49:08 UTC,
c,
verify,
result: Passed
int abs(int x)
{
return (x < 0) ? -x : x;
}
int min_abs_sum ( int A[], int n )
{
int *count = (int*)calloc(105, sizeof(int));
int i;
for (i = 0; i < n; i++)
count[abs(A[i])]++;
int suma = 0;
for (i = 100; i >= 0; i--)
while (count[i]-- > 0)
suma = abs(suma-i);
return suma;
}
Analysis
Code: 14:49:14 UTC,
c,
final,
score:
100
int abs(int x)
{
return (x < 0) ? -x : x;
}
int min_abs_sum ( int A[], int n )
{
int *count = (int*)calloc(105, sizeof(int));
int i;
for (i = 0; i < n; i++)
count[abs(A[i])]++;
int suma = 0;
for (i = 100; i >= 0; i--)
while (count[i]-- > 0)
suma = abs(suma-i);
return suma;
}Analysis summary
Analysis
Detected time complexity:
O(n*|max_value|^2)
expand all
Assessment tests
1.
0.004 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.004 s
OK
1.
0.004 s
OK
1.
0.001 s
OK
1.
0.004 s
OK
1.
0.004 s
OK
1.
0.004 s
OK
1.
0.008 s
OK
1.
0.008 s
OK