Link to the Problem: Number of Steps
Intuition
Code
It is giving me WA on Input #4 and TLE on Input #5 and Input #6. I tried for hours but was unable to find a problem with my solution. And even in the worst-case scenario where
n = 5000
every ai=5000
every bi = 1
It has an O(n*max(ai)) solution which should be feasible for these constraints. A hint or Advice is appreciated.
There is an issue with the test data of this problem.
In input #5, $$$a_{4914} = b_{4914} = 0$$$.
In input #6, $$$b_{1153} = b_{4400} = 0$$$ while $$$a_{1153} = a_{4400} = 500$$$.
This implies that the correct constraints should be
$$$1 \leq n \leq 5000$$$ and $$$0 \leq a_{i}, b_{i} \leq 5000$$$
A simple brute force solution for the problem should be as follows. Let the final value of all elements in the array be equal to $$$c$$$, and the minimum value of $$$a_{i}$$$ for $$$1 \leq i \leq n$$$ be equal to $$$m$$$. Since the only operation allowed is to decrease $$$a_i$$$ by $$$b_i$$$, the maximum value of $$$c$$$ can never be larger than $$$m$$$. Hence, it is sufficient to iterate over all possible values of $$$c$$$, where $$$0 \leq c \leq m$$$, and find for each value of $$$c$$$ the summation of the number of steps $$$x_i$$$, where $$$x_i \geq 0$$$, such that the final value of $$$a_{i}$$$ is equal to $$$c$$$. By definition, $$$c = a_i - x_i \times b_i$$$, which means that $$$x_i = \frac{a_i-c}{b_i}$$$. Since $$$x_{i}$$$ has to be an non-negative integer number, a necessary condition that the final value of the array elements is equal to $$$c$$$ is that $$$a_i-c$$$ has to be divisible by $$$b_i$$$ for all $$$1 \leq i \leq n$$$, where $$$b_i \neq 0$$$. Finally, if $$$b_{i} = 0$$$ for some $$$1 \leq i \leq n$$$, then it is not possible to decrement $$$a_{i}$$$, and the final value of the array elements has to be equal to $$$a_{i}$$$. If $$$a_i = 5000, b_i = 1$$$ for all $$$1 \leq i \leq n$$$, then this brute force solution should run for $$$5000\times5000$$$ iterations, where each iteration requires $$$O(1)$$$ operation.
Thanks a lot.
With pleasure.