Tasks Details
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
The submission is being evaluated.
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–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}