DBMB and the Array

Let

$A = \sum_{i=1}^{n} a_i$

be the current sum of the array.

The key observation is that the chosen index does not matter for the total sum. One operation adds $x$ to exactly one element, so the total sum increases by exactly $x$.

After doing $k$ operations, where $k \ge 0$, the sum becomes

$A + kx.$

We need this to equal $s$:

$A + kx = s.$

Rearranging gives

$kx = s - A.$

So there are only two things to check:

• $s - A \ge 0$, because we cannot decrease the sum. If the array is already too large, tough luck.
• $s - A$ must be divisible by $x$, because every operation changes the sum in chunks of size $x$.

Therefore, the array can become appealing iff

$s \ge A \quad \text{and} \quad (s - A) \bmod x = 0.$

Why this is enough: if those conditions hold, let

$k = \frac{s - A}{x}.$

This is a nonnegative integer. We can simply apply the operation $k$ times to any element, say $a_1$. The total sum becomes exactly $s$. No need for fancy distribution among elements. The array elements have no upper bound after operations, so stacking all operations onto one index is totally fine.

Edge cases:

• If $A = s$, then $k = 0$, and doing zero operations is allowed, so the answer is YES.
• If $A > s$, answer is always NO.
• If $x = 1$, then every larger or equal target sum is reachable.

Complexity is tiny:

$O(n)$

per test case to compute the sum, with

$O(1)$

extra memory.