Tasks Details
hard
1.
MinAbsSum
Given array of integers, find the lowest absolute sum of elements.
Task Score
90%
Correctness
83%
Performance
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] = -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 JavaScript
Time spent on task 1 minutes
Notes
not defined yet
Code: 21:13:48 UTC,
java,
autosave
Code: 21:13:58 UTC,
js,
autosave
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
A.forEach((value, index, array) => {
array[index] = Math.abs(value)
})
const maxValue = Math.max(...A)
const sameValuesCount = new Array(maxValue + 1)
sameValuesCount.fill(0)
A.forEach((value) => {
++sameValuesCount[value]
})
const maxSum = sameValuesCount.reduce((previousValue, currentValue, currentIndex) => {
return previousValue + currentValue * currentIndex
}, 0)
const dp = new Array(maxSum + 1)
dp.fill(-1)
dp[0] = 0
sameValuesCount.forEach((countValue, countIndex) => {
if (countValue > 0) {
dp.forEach((dpValue, dpIndex, dpArray) => {
if (dpValue >= 0) {
dpArray[dpIndex] = countValue
} else if (dpIndex >= countIndex && dpArray[dpIndex - countIndex] > 0) {
dpArray[dpIndex] = dpArray[dpIndex - countIndex] - 1
}
})
}
})
let result = maxSum
for (let i = 0; i < Math.floor(maxSum / 2) + 1; ++i) {
if (dp[i] >= 0) {
result = Math.min(result, maxSum - 2 * i)
}
}
return result
}
Code: 21:14:04 UTC,
js,
autosave
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
A.forEach((value, index, array) => {
array[index] = Math.abs(value)
})
const maxValue = Math.max(...A)
const sameValuesCount = new Array(maxValue + 1)
sameValuesCount.fill(0)
A.forEach((value) => {
++sameValuesCount[value]
})
const maxSum = sameValuesCount.reduce((previousValue, currentValue, currentIndex) => {
return previousValue + currentValue * currentIndex
}, 0)
const dp = new Array(maxSum + 1)
dp.fill(-1)
dp[0] = 0
sameValuesCount.forEach((countValue, countIndex) => {
if (countValue > 0) {
dp.forEach((dpValue, dpIndex, dpArray) => {
if (dpValue >= 0) {
dpArray[dpIndex] = countValue
} else if (dpIndex >= countIndex && dpArray[dpIndex - countIndex] > 0) {
dpArray[dpIndex] = dpArray[dpIndex - countIndex] - 1
}
})
}
})
let minSum = maxSum
for (let i = Math.floor(maxSum / 2); i >= 0; --i) {
if (dp[i] >= 0) {
minSum = Math.min(minSum, maxSum - 2 * i)
break
}
}
return minSum
}
Code: 21:14:05 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
A.forEach((value, index, array) => {
array[index] = Math.abs(value)
})
const maxValue = Math.max(...A)
const sameValuesCount = new Array(maxValue + 1)
sameValuesCount.fill(0)
A.forEach((value) => {
++sameValuesCount[value]
})
const maxSum = sameValuesCount.reduce((previousValue, currentValue, currentIndex) => {
return previousValue + currentValue * currentIndex
}, 0)
const dp = new Array(maxSum + 1)
dp.fill(-1)
dp[0] = 0
sameValuesCount.forEach((countValue, countIndex) => {
if (countValue > 0) {
dp.forEach((dpValue, dpIndex, dpArray) => {
if (dpValue >= 0) {
dpArray[dpIndex] = countValue
} else if (dpIndex >= countIndex && dpArray[dpIndex - countIndex] > 0) {
dpArray[dpIndex] = dpArray[dpIndex - countIndex] - 1
}
})
}
})
let minSum = maxSum
for (let i = Math.floor(maxSum / 2); i >= 0; --i) {
if (dp[i] >= 0) {
minSum = Math.min(minSum, maxSum - 2 * i)
break
}
}
return minSum
}
Analysis
Code: 21:14:11 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
A.forEach((value, index, array) => {
array[index] = Math.abs(value)
})
const maxValue = Math.max(...A)
const sameValuesCount = new Array(maxValue + 1)
sameValuesCount.fill(0)
A.forEach((value) => {
++sameValuesCount[value]
})
const maxSum = sameValuesCount.reduce((previousValue, currentValue, currentIndex) => {
return previousValue + currentValue * currentIndex
}, 0)
const dp = new Array(maxSum + 1)
dp.fill(-1)
dp[0] = 0
sameValuesCount.forEach((countValue, countIndex) => {
if (countValue > 0) {
dp.forEach((dpValue, dpIndex, dpArray) => {
if (dpValue >= 0) {
dpArray[dpIndex] = countValue
} else if (dpIndex >= countIndex && dpArray[dpIndex - countIndex] > 0) {
dpArray[dpIndex] = dpArray[dpIndex - countIndex] - 1
}
})
}
})
let minSum = maxSum
for (let i = Math.floor(maxSum / 2); i >= 0; --i) {
if (dp[i] >= 0) {
minSum = Math.min(minSum, maxSum - 2 * i)
break
}
}
return minSum
}
Analysis
Code: 21:14:13 UTC,
js,
final,
score:
90
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A) {
A.forEach((value, index, array) => {
array[index] = Math.abs(value)
})
const maxValue = Math.max(...A)
const sameValuesCount = new Array(maxValue + 1)
sameValuesCount.fill(0)
A.forEach((value) => {
++sameValuesCount[value]
})
const maxSum = sameValuesCount.reduce((previousValue, currentValue, currentIndex) => {
return previousValue + currentValue * currentIndex
}, 0)
const dp = new Array(maxSum + 1)
dp.fill(-1)
dp[0] = 0
sameValuesCount.forEach((countValue, countIndex) => {
if (countValue > 0) {
dp.forEach((dpValue, dpIndex, dpArray) => {
if (dpValue >= 0) {
dpArray[dpIndex] = countValue
} else if (dpIndex >= countIndex && dpArray[dpIndex - countIndex] > 0) {
dpArray[dpIndex] = dpArray[dpIndex - countIndex] - 1
}
})
}
})
let minSum = maxSum
for (let i = Math.floor(maxSum / 2); i >= 0; --i) {
if (dp[i] >= 0) {
minSum = Math.min(minSum, maxSum - 2 * i)
break
}
}
return minSum
}
Analysis summary
The following issues have been detected: runtime errors.
For example, for the input [] the solution terminated unexpectedly.
Analysis
Detected time complexity:
O(N * max(abs(A))**2)
expand all
Correctness tests
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
1.
0.072 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
RangeError: Invalid array length
at solution (solution.js:12:29)
at solutionWrapper (/tmp/exec.js:402:28)
at Promise.resolve.then (/tmp/exec.js:428:24)
at <anonymous>
at process._tickCallback (internal/process/next_tick.js:188:7)
at Function.Module.runMain (module.js:686:11)
at startup (bootstrap_node.js:187:16)
at bootstrap_node.js:608:3
2.
0.072 s
OK
1.
0.072 s
OK
2.
0.072 s
OK
3.
0.072 s
OK
expand all
Performance tests
1.
0.080 s
OK
2.
0.072 s
OK
1.
0.076 s
OK
2.
0.072 s
OK
1.
0.140 s
OK
2.
0.072 s
OK
1.
0.092 s
OK
1.
0.200 s
OK
2.
0.072 s
OK