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:

function solution(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 JavaScript

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 16:46:34 UTC, js, 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

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  if (A.length === 0) return 0;
  const B = A.map((element) => Math.abs(element));
  const M = Math.max(...B);
  const S = B.reduce((sum, element) => sum + element);
  const count = Array.from({ length: M + 1 }, () => 0);
  B.forEach((element) => {
    count[element]++;
  });
  const dp = Array.from({ length: S + 1 }, () => -1);
  dp[0] = 0;
  for (let i = 0; i <= M; i++) {
    if (count[i] !== 0) {
      for (let j = 0; j <= S; j++) {
        if (dp[j] >= 0) {
          dp[j] = count[i];
        } else if (j >= i && dp[j - i] > 0) {
          dp[j] = dp[j - i] - 1;
        }
      }
    }
  }
  const target = S / 2;
  let diff = Number.MAX_VALUE;
  let result;
  for (let j = 0; j <= S; j++) {
    if (dp[j] !== -1 && Math.abs(j - target) < diff) {
      result = j;
      diff = Math.abs(j - target);
    }
  }
  result = Math.abs(S - 2 * result);
  return result;
}

Analysis

▶

example1
example test

✔

Code: 16:46:37 UTC, js, 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

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  if (A.length === 0) return 0;
  const B = A.map((element) => Math.abs(element));
  const M = Math.max(...B);
  const S = B.reduce((sum, element) => sum + element);
  const count = Array.from({ length: M + 1 }, () => 0);
  B.forEach((element) => {
    count[element]++;
  });
  const dp = Array.from({ length: S + 1 }, () => -1);
  dp[0] = 0;
  for (let i = 0; i <= M; i++) {
    if (count[i] !== 0) {
      for (let j = 0; j <= S; j++) {
        if (dp[j] >= 0) {
          dp[j] = count[i];
        } else if (j >= i && dp[j - i] > 0) {
          dp[j] = dp[j - i] - 1;
        }
      }
    }
  }
  const target = S / 2;
  let diff = Number.MAX_VALUE;
  let result;
  for (let j = 0; j <= S; j++) {
    if (dp[j] !== -1 && Math.abs(j - target) < diff) {
      result = j;
      diff = Math.abs(j - target);
    }
  }
  result = Math.abs(S - 2 * result);
  return result;
}

Analysis

▶

example1
example test

✔

Code: 16:46:39 UTC, js, 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

function solution(A) {
  // write your code in JavaScript (Node.js 8.9.4)
  if (A.length === 0) return 0;
  const B = A.map((element) => Math.abs(element));
  const M = Math.max(...B);
  const S = B.reduce((sum, element) => sum + element);
  const count = Array.from({ length: M + 1 }, () => 0);
  B.forEach((element) => {
    count[element]++;
  });
  const dp = Array.from({ length: S + 1 }, () => -1);
  dp[0] = 0;
  for (let i = 0; i <= M; i++) {
    if (count[i] !== 0) {
      for (let j = 0; j <= S; j++) {
        if (dp[j] >= 0) {
          dp[j] = count[i];
        } else if (j >= i && dp[j - i] > 0) {
          dp[j] = dp[j - i] - 1;
        }
      }
    }
  }
  const target = S / 2;
  let diff = Number.MAX_VALUE;
  let result;
  for (let j = 0; j <= S; j++) {
    if (dp[j] !== -1 && Math.abs(j - target) < diff) {
      result = j;
      diff = Math.abs(j - target);
    }
  }
  result = Math.abs(S - 2 * result);
  return result;
}

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

✔