Tasks Details
hard
1.
MinAbsSum
Given array of integers, find the lowest absolute sum of elements.
Task Score
86%
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:
class Solution { public int solution(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].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Total time used 9 minutes
Effective time used 9 minutes
Notes
not defined yet
Task timeline
Code: 17:25:44 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:29:01 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:30:00 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:32:03 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:32:19 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = A[i];
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:32:30 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:32:39 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:32:48 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:32:57 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis
Code: 17:33:03 UTC,
java,
final,
score:
86
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
import java.math.*;
import java.lang.Integer;
import java.util.*;
class Solution {
int findmax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
return maxval;
}
int[] removemax(int[] A)
{
int maxval = Integer.MIN_VALUE;
int i,maxi;
maxi = -1;
for(i=0; i< A.length; i++)
{
if( Math.abs(A[i]) > maxval )
{
maxval = Math.abs(A[i]);
maxi = i;
}
}
int[] newArray;
int k;
k=0;
newArray= new int[A.length-1];
for(i=0; i< A.length; i++)
{
if( i != maxi )
newArray[k++] = A[i];
}
return newArray;
}
int min_abs_sum ( int[] A ) {
if( A.length == 0 ) return 0;
int i,j;
int maxval = Integer.MIN_VALUE;
int maxi = 0;
int newval;
maxval= findmax(A);
A = removemax(A);
while( A.length > 0 )
{
newval= findmax(A);
A = removemax(A);
int val1 = Math.abs(maxval-newval);
int val2 = Math.abs(maxval+newval);
if( val1 < val2 )
maxval = val1;
else
maxval = val2;
}
return maxval;
}
}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(n^2*|max_value|)
expand all
Assessment tests
1.
0.348 s
OK
1.
0.356 s
OK
1.
0.348 s
OK
1.
0.344 s
OK
1.
0.364 s
OK
1.
0.348 s
OK
1.
0.424 s
OK
1.
0.348 s
OK
1.
0.352 s
OK
1.
0.364 s
OK
1.
0.488 s
OK
1.
1.956 s
TIMEOUT ERROR,
running time: >1.96 sec., time limit: 1.54 sec.
1.
2.220 s
TIMEOUT ERROR,
running time: >2.22 sec., time limit: 1.58 sec.