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:
def 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].
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
if len(A) == 0:
return 0
if len(A) == 1:
return A[0]
AS = sorted(map(abs, A), reverse=True)
sum_val = sum(AS)
c_sum = 0
closest = sum_val
target = sum_val // 2
for a in AS:
diff = target - c_sum - a
if 0 <= diff < closest:
c_sum += a
closest = diff
return sum_val - 2 * c_sum
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
if len(A) == 0:
return 0
if len(A) == 1:
return A[0]
AS = sorted(map(abs, A), reverse=True)
sum_val = sum(AS)
c_sum = 0
closest = sum_val
target = sum_val // 2
for a in AS:
diff = target - c_sum - a
if 0 <= diff < closest:
c_sum += a
closest = diff
return sum_val - 2 * c_sum
[-5, 8, -1]
[0, -5, 3, 2]
[14, -4, 5]
[0, 12, 10, 15]
function result: 2
function result: 0
function result: 5
function result: 7
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
if len(A) == 0:
return 0
if len(A) == 1:
return A[0]
AS = sorted(map(abs, A), reverse=True)
sum_val = sum(AS)
c_sum = 0
closest = sum_val
target = sum_val // 2
for a in AS:
diff = target - c_sum - a
if 0 <= diff < closest:
c_sum += a
closest = diff
return sum_val - 2 * c_sum
[-5, 8, -1]
[0, -5, 3, 2]
[14, -4, 5]
[0, 12, 10, 15]
[-1, -2, -3]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
if len(A) == 0:
return 0
if len(A) == 1:
return A[0]
AS = sorted(map(abs, A), reverse=True)
sum_val = sum(AS)
c_sum = 0
closest = sum_val
target = sum_val // 2
for a in AS:
diff = target - c_sum - a
if 0 <= diff < closest:
c_sum += a
closest = diff
return sum_val - 2 * c_sum
[-5, 8, -1]
[0, -5, 3, 2]
[14, -4, 5]
[0, 12, 10, 15]
[-1, -2, -3]
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
if len(A) == 0:
return 0
if len(A) == 1:
return A[0]
AS = sorted(map(abs, A), reverse=True)
sum_val = sum(AS)
c_sum = 0
closest = sum_val
target = sum_val // 2
for a in AS:
diff = target - c_sum - a
if 0 <= diff < closest:
c_sum += a
closest = diff
return sum_val - 2 * c_sum
The following issues have been detected: wrong answers.