0
$\begingroup$

So hey, I've recently found this problem online and I tried hard to solve but couldn't found an efficient solution. The problem statement is:

Given and two integers $n$ and $k$ and an array $A$ containing $n$ pairs of integers of the form $(a, b)$ and $d$ defined as $d = |\sum_{x \in E} x[1] -x[0]| $ where is $E$ is a subset of $A$ containing exactly $k$ elements. Find the minimum value of $d$.

To illustrate the problem, consider $n = 3$, $k = 2$, $A = [(2, 1), (0, 2), (1, 2)]$.

The minimum value of $d$ is $0$. We can pick $E = [(1, 2), (2, 1)]$ containing $k = 2$ values of $A$ then $d = |(1 - 2) + (2 - 1)| = |0| = 0$.

I tried to solve this problem but only came up with the brute force solution which is terrible in terms of time complexity.

How can one solve this problem efficiently ?

$\endgroup$
2
$\begingroup$

I'm unable to add comments but I think this problem can be simplified to:

B = []
for pair in A:
    B.append(pair[0] - pair[1])

min_sum(B, k)

min_sum returns k elements that add up to give the smallest number possible (absolute value). This (at least to me) feels easier to work with.

$\endgroup$
  • 1
    $\begingroup$ And this in turn is almost the subset sum problem. $\endgroup$ – Gribouillis Aug 3 '17 at 18:26
  • $\begingroup$ Can you explain how to reduce to subset sum problem ? $\endgroup$ – Noctisdark Aug 3 '17 at 18:35
  • $\begingroup$ @Noctisark Using Izaan's notation, the subset sum problem can be formulated as "Is any of min_sum(B, 1), ...,min_sum(B, N) equal to zero?". $\endgroup$ – Gribouillis Aug 3 '17 at 21:21
  • $\begingroup$ I actually thought about it and said it would likely timeout, thanks for the answer, really :). $\endgroup$ – Noctisdark Aug 4 '17 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.