What is the best time complexity of checking the inequality $a_1x_1 + \cdots + a_mx_m \le K$ to have a non-negative integer solution?

Question

Consider $$a_1x_1 + \cdots + a_mx_m \le K$$

with $a_1, a_2, \ldots , a_m$ and $K$ being integers.

I only need to know if the inequality has an integer solution or not.

It means that there is no need to find all the (probable available) solutions.

Actually, I need to know the best possible approach to address this problem according to its time complexity.

Answer 1

Under the condition that every $x_k$ is non-negative, if $K \geq 0$ then set $x_1 = \cdots = x_m = 0.$ Then $a_1x_1 + \cdots + a_mx_m = 0 \leq K$.

If $K < 0$ and one of the coefficients $a_k$ is negative, set $x_k \geq \frac{K}{a_k}$ (so that $a_kx_k \leq K$) and set all other $x_i=0$.

If $K < 0$ and $a_k \geq 0$ for every $k$, then there is no solution, since necessarily $a_1x_1 + \cdots + a_mx_m \geq 0 > K.$

So the best case is one step to determine that $K \geq 0$. The worst case is $m+1$ steps: one step to determine that $K < 0$, $m-1$ steps to determine that $m-1$ of the coefficients $a_k$ are all non-negative, and one more step to determine whether the remaining coefficient is negative.