If the question is to convert all 0 array to target array by adding any integer x, we can use coordinate compression on target array.

And then answer is summation of max(a[i] — a[i-1],0) for all i assuming a[-1] = 0

Is it always possible to convert array $$$A$$$ into $$$B$$$ with only positive $$$K$$$?

Anyway, when there is no restriction on $$$K$$$, I think it can be solved in this way assuming $$$C_i = B_i - A_i$$$:

int fun(int l,int r,int x)
{
    int p=rmq(l,r);              // p = position of the minimum value in the subarray c[l...r]
    int o=(c[p]>0 && x<c[p]);    // if c[p] is not zero and greater than the previous minimum, count 1
    if(l<p) o+=fun(l,p-1,c[p]);  // call on the left side
    if(r>p) o+=fun(p+1,r,c[p]);  // call on the right side
    return o;                    // return the answer
}

Final answer: fun(0,n-1,c[rmq(0,n-1)]-1)

Please tell me if you have a counter case for this approach.

I think I have a solution for positive K. (EDIT2: As clyring pointed out, this solution is wrong. )

Let C[i] be B[i] — A[i]. In other words, C[i] shows us how much we need to increase A[i]. If there is an index i such that C[i] < 0, then there is no solution. Otherwise, let’s maintain a set. For every index i, this set will store the numbers by which we can increase A[i] without using a new operation. We firstly add 0 to this set. Say that the variable storing our answer is ans (initialised to 0). For every i from 1 to n, if C[i-1] < C[i] (we suppose C[0] is 0), we increment ans, else, we remove from the set all the numbers that are strictly bigger than C[i] and if we don’t find the value C[i] in the set, we increment ans. At every step, we add to the set C[i] — every value currently in the set.

For variation 2 of the problem, I don't have a solution handy, but here is some insight:

Suppose for convenience that the arrays $$$A$$$ and $$$B$$$ naturally have indices from $$$1$$$ to $$$N$$$, and that they have been extended to have $$$A[0] = B[0] = A[N+1] = B[N+1] = 0$$$. I claim that for any $$$k \in \mathbb{Z}, 0 \leq k \leq N$$$, there exists a solution with $$$k$$$ operations if and only if the multiset $$$S = \{ (B[i] - A[i]) - (B[i-1] - A[i-1]) : i \in \mathbb{Z},\, 1 \leq i \leq N+1 \}$$$ can be partitioned into $$$N+1-k$$$ nonempty multisets each with sum zero.

To see this, note that adding $$$x$$$ to every position from $$$L$$$ to $$$R$$$ in the original problem basis amounts to adding $$$x$$$ in position $$$L$$$ and $$$-x$$$ in position $$$R+1$$$ in a backwards-differences basis. Thus, for any sequence of $$$k$$$ operations that transforms $$$A$$$ into $$$B$$$, if we consider the graph $$$G$$$ with vertices numbered $$$1$$$ to $$$N+1$$$ and with an edge between $$$L$$$ and $$$R+1$$$ for every operation used, the sum

must be equal to $$$0$$$ for every connected component $$$C$$$ of the graph $$$G$$$. These connected components thus give us a partition of $$$S$$$ into at least $$$N - 1 - E$$$ nonempty multisets with sum zero, where $$$E$$$ is the number of edges, which is at most the number of operations $$$k$$$. We can then merge a few of these if $$$E < k$$$ to get exactly $$$N + 1 - k$$$ multisets.

In the reverse direction, given a partition of $$$S$$$ into $$$N + 1 - k$$$ nonempty multisets each with sum zero, we can select $$$k$$$ edges between pairs of numbers between $$$1$$$ and $$$N+1$$$ to give us a graph with connected components corresponding to this partition, and after a little bit of fairly simple linear algebra there will be a unique selection of integer weights $$$x$$$ for the operations on the $$$k$$$ intervals corresponding to these edges that will transform $$$A$$$ into $$$B$$$.

EDIT: A similar idea works for variation 1 of the problem, but with partitions of $$$\mathbb{Z} \cap [1, N+1]$$$ into nonempty sets $$$S$$$ such that the following sum is $$$0$$$ for $$$j = \max S$$$ and non-negative for all other $$$j \in S$$$:

The argument is more or less the same.

there is a similar question had come in a company OA, in which we have to do equal both array A and B but performing a operation on A or B.

in a operation you can select a subarray of selected array ( A or B ) and increase this subarray by 1 or decrease by 1

Task : find the minimum number of operation to do this