Given a list of candidates, can we hit target value in linear time?

Question

I recently was asked this question. I bombed it and I'd love some help with it. The question went like this:

You're given a list of numbers. The numbers are all positive integers. So imagine them something like this:

[x_0, x_1, ..., x_{n-2}, x_{n-1}]

So we have n numbers. There's no guarantee that the numbers are different. We also have a target value. Let's call this X. X is also a positive integer.

The goal is to output a boolean just True/False if we can express the target number, X, in terms of the candidate in the following form:

a * x_0 + b * x_1 + ... 

The only constraint for the coefficients is that they also have to be positive integers greater than or equal to 0.

You can get the answer in linear time by doing just a bit of math with your candidate numbers. However, I was curious if I could see the algorithm a bit more fleshed out. It doesn't need to be coded up - I can do that - but I still don't exactly have the algorithm. I was thinking maybe something similar in approach to the Sieve of Eratosthenes or maybe even the Diophantine Equation. Regardless, I couldn't find a clean writeup of the solution anywhere online and was curious if this problem as been explored more.

Does anyone have any thoughts? Thanks again! Really appreciate your help!

Answer 1

A solution using a sieve could look something like this:

Create an array of boolean with size X+1, with zero set to true and all other values set to false. Then, for every value x_i

• skip to the next value if x_i is already set to true (a combination of previous numbers can be used to form x_i and all its multiples).
• else, iterate over the array (from 0 to X-x_i) and for every value x_k which is true, set x_k+x_i to true.
• as soon as value X is set to true, return true.

Sorting the values from small to large first may increase the chance that you can skip some values.

Example:

X = 21, x = {4, 6, 8, 10, 11, 13, 15}  

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21  
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

x = 4:  
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21  
{1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0}

x = 6:  
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21  
{1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0}

x = 8: skip

x = 10: skip

x = 11:
 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21  
{1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1}
10 + 11 = 21  ->  return true

The worst case (no values skipped, result is false) complexity of this is N×X, while in the best case (the first value for x divides X) a solution is found nearly instantly. Calculating an average case complexity is not straightforward, I fear.