Test results - Codility

Tasks Details

hard

1. MinAbsSum

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

100%

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] = -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 Java 8

Time spent on task 1 minutes

Notes

not defined yet

Code: 04:32:14 UTC, java, 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

import java.util.*;

class Solution {
    
    private int[] absA;
    private int sum;
    private Map<Integer, Integer> countMap = new HashMap<>();
    private int[] subset;

    public int solution(int[] A) {
        this.absA = getAbs(A);
        this.sum = getSum(absA);
        this.countMap = getCountMap(absA);
        this.subset = new int[Math.max(sum, 1)];

        Arrays.fill(subset, -1);
        subset[0] = 0;

        for (int key : countMap.keySet()) {
            for (int i=0; i<sum/2+1; i++) {
                if (subset[i] >= 0) {
                    subset[i] = countMap.get(key);
                } else if (i >= key && subset[i - key] > 0) {
                    subset[i] = subset[i - key] - 1;
                }
            }
        }

        int res = sum;
        for (int i=0; i<sum/2+1; i++) {
            if (subset[i] >= 0) {
                res = Math.min(res, sum - i * 2);
            }
        }
        
        return res;
    }

    private int[] getAbs(int[] A) {
        int[] absA = new int[A.length];
        for (int i=0; i<A.length; i++) {
            absA[i] = Math.abs(A[i]);
        }

        return absA;
    }

    private int getSum(int[] A) {
        int sum = 0;
        for (int i=0; i<A.length; i++) {
            sum += A[i];
        }

        return sum;
    }

    private Map<Integer, Integer> getCountMap(int[] A) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i=0; i<A.length; i++) {
            countMap.put(A[i], countMap.getOrDefault(A[i], 0) + 1);
        }

        return countMap;
    }
}

Code: 04:32:17 UTC, java, final, score: 100

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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

import java.util.*;

class Solution {
    
    private int[] absA;
    private int sum;
    private Map<Integer, Integer> countMap = new HashMap<>();
    private int[] subset;

    public int solution(int[] A) {
        this.absA = getAbs(A);
        this.sum = getSum(absA);
        this.countMap = getCountMap(absA);
        this.subset = new int[Math.max(sum, 1)];

        Arrays.fill(subset, -1);
        subset[0] = 0;

        for (int key : countMap.keySet()) {
            for (int i=0; i<sum/2+1; i++) {
                if (subset[i] >= 0) {
                    subset[i] = countMap.get(key);
                } else if (i >= key && subset[i - key] > 0) {
                    subset[i] = subset[i - key] - 1;
                }
            }
        }

        int res = sum;
        for (int i=0; i<sum/2+1; i++) {
            if (subset[i] >= 0) {
                res = Math.min(res, sum - i * 2);
            }
        }
        
        return res;
    }

    private int[] getAbs(int[] A) {
        int[] absA = new int[A.length];
        for (int i=0; i<A.length; i++) {
            absA[i] = Math.abs(A[i]);
        }

        return absA;
    }

    private int getSum(int[] A) {
        int sum = 0;
        for (int i=0; i<A.length; i++) {
            sum += A[i];
        }

        return sum;
    }

    private Map<Integer, Integer> getCountMap(int[] A) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i=0; i<A.length; i++) {
            countMap.put(A[i], countMap.getOrDefault(A[i], 0) + 1);
        }

        return countMap;
    }
}

Analysis summary

The solution obtained perfect score.

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

✔

▶

medium2
multiples of 10 + 5

✔

▶

big1
multiples of 5 + 42

✔

▶

big3
all 4s and one 3

✔

▶

big4
multiples of 10

✔