Test results - Codility

Tasks Details

hard

1. MinAbsSum

Given array of integers, find the lowest absolute sum of elements.

90%

100%

80%

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] = -2

your 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].

Solution

Programming language used C++

Time spent on task 4 minutes

Notes

not defined yet

Task timeline

Code: 07:11:37 UTC, cpp, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

// you can use includes, for example:
#include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int n = A.size();
    
    if (n == 0)
        return 0;
    if (n == 1)
        return abs(A[0]);
    
    for (int i = 0; i < n; i++){
        A[i] = abs(A[i]);
    }
    
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    
    int sum1 = A[0];
    int sum2 = A[1];
    
    for (int i = 2; i < n; i++){
        if (sum1 < sum2)
            sum1 += abs(A[i]);
        else
            sum2 += abs(A[i]);
    }
    
    int tmp = abs(sum1 - sum2);
    sum1 = A[0] + A[1];
    sum2 = 0;
    for (int i = 2; i < n; i++){
        if (sum1 < sum2)
            sum1 += abs(A[i]);
        else
            sum2 += abs(A[i]);
    }
    
    return abs(sum1 - sum2) < tmp ? abs(sum1 - sum2) : tmp;
}

Analysis

▶

example1
example test

✔

Code: 07:11:45 UTC, cpp, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

// you can use includes, for example:
#include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int n = A.size();
    
    if (n == 0)
        return 0;
    if (n == 1)
        return abs(A[0]);
    
    for (int i = 0; i < n; i++){
        A[i] = abs(A[i]);
    }
    
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    
    int sum1 = A[0];
    int sum2 = A[1];
    
    for (int i = 2; i < n; i++){
        if (sum1 < sum2)
            sum1 += abs(A[i]);
        else
            sum2 += abs(A[i]);
    }
    
    int tmp = abs(sum1 - sum2);
    sum1 = A[0] + A[1];
    sum2 = 0;
    for (int i = 2; i < n; i++){
        if (sum1 < sum2)
            sum1 += abs(A[i]);
        else
            sum2 += abs(A[i]);
    }
    
    return abs(sum1 - sum2) < tmp ? abs(sum1 - sum2) : tmp;
}

Analysis

▶

example1
example test

✔

Code: 07:11:51 UTC, cpp, final, score: 90

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

// you can use includes, for example:
#include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int n = A.size();
    
    if (n == 0)
        return 0;
    if (n == 1)
        return abs(A[0]);
    
    for (int i = 0; i < n; i++){
        A[i] = abs(A[i]);
    }
    
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    
    int sum1 = A[0];
    int sum2 = A[1];
    
    for (int i = 2; i < n; i++){
        if (sum1 < sum2)
            sum1 += abs(A[i]);
        else
            sum2 += abs(A[i]);
    }
    
    int tmp = abs(sum1 - sum2);
    sum1 = A[0] + A[1];
    sum2 = 0;
    for (int i = 2; i < n; i++){
        if (sum1 < sum2)
            sum1 += abs(A[i]);
        else
            sum2 += abs(A[i]);
    }
    
    return abs(sum1 - sum2) < tmp ? abs(sum1 - sum2) : tmp;
}

Analysis summary

The following issues have been detected: wrong answers.

Analysis

Detected time complexity:

O(N * max(abs(A))**2)

▶

example1
example test

✔

▶

simple1
simple 1

✔

▶

simple2
simple 2

✔

▶

simple3
simple 3

✔

▶

range
range 2..20

✔

▶

extreme
empty and single element

✔

▶

functional
small functional test

✔

▶

medium1
medium random

✘

WRONG ANSWER
got 4 expected 0

▶

medium2
multiples of 10 + 5

✔

▶

big1
multiples of 5 + 42

✔

▶

big3
all 4s and one 3

✔

▶

big4
multiples of 10

✔