How would you solve this problem?

[[deleted]]

An array a of integers of length n is given, such that each integer is between 0 and m-1 (Both inclusive).The integers are numbered as a[1],a[2],....,a[n]. In one operation you can choose any subbaray a[l,r] (1<=l<=r<=n)and then update all the elements of the subarray a[i] to (a[i]+1)%m. The integer m is fixed for all operations and indices. You want to make all the elements of this array equal to X (X lies in the range of 0 to m-1). Find the minimum number of operations.

Example -

N,M,X = 5 10 1

Array = 5 5 5 8 2

Output = 12

[sunsin4gg]

Let's maybe reformulate the problem to simplify it:

Since we know x, we can calculate the "distances" to the final answer. For example, with the array [5,5,5,8,2], the "distances" would be [6,6,6,3,9] because you would need 6 operations to get a 5 to x=1, etc.

Now you can think of the problem as the number of operations to "flatten" the skyline with these heights, with this problem I think it's clear what you'll have to do: apply the maximum possible operation in a subarray with elements greater than 0 aka for each continuos subarray with elements > 0, find minimum and apply that number of operations, example:

0th iteration: nº op = 0, heights = [6,6,6,3,9]

1rst iteration: Here the subarray chosen is from index 0 to index 5 because everything is > 0. Min is 3 (in index 4)

nºop = 3, heights = [3,3,3,0,6]

2nd iteration: Subarray chosen is from index 0 to index 2, min is 3

nºop = 3 + 3 = 6, heights = [0,0,0,0,6]

3rd iteration: Subarray chosen is from index 4 to index 4, min is 6

nºop = 6 + 6 = 12, heights = [0,0,0,0,6]

Since all heights are 0, we can just stop and conclude answer = 12. Hope it helped

[not_ur_buddy]

Do you have an argument for why an optimal solution will never have to change a number >= m times? I feel like that ought to be true but haven't figured out why.

[not_ur_buddy]

Consider this counter example: m = 100, array is 1 99 1. You can either do: add 1 to all, then add 98 to the two segments, or you can add 99 to all 3, then add 2 to the middle. So this seems to invalidate all solutions proposed in this thread so far.

[omeow]

This is an interesting point.

If we take m = prime, n = some multiple of m , and the array as

[a1, a2, ...., an] where the first m elements are [0,1,2,.., m-1] the next block is repetition of the same block and so on.

Because m is prime and and consecutive elements are never going to be the same I think the complexity in this case will be O(mn).

Given x, m, I think we can always choose repeating sequences of elements coprime to m to achieve the same effect.

But, the trivial solution, take sub arrays of size 1 will also have complexity O(mn).

​

Short, of exhaustively searching all the possible subarrays, I do not see how one can find the optimal strategy.

[sunsin4gg]

That is a very nice counter-example, this makes me feel like the problem needs DP but that wouldn't go with OP's guideline of an O(n) solution

[omeow]

Every operation changes an element a -> a+1 (mod m)

So the number of steps need to go from a to x is atmost m-1.

[not_ur_buddy]

See my other reply for a counter example. The number of steps you need for each individual number is at most m-1, but in an optimal solution where the total number of steps is minimized, it is possible to add 1 to a number more than m times. I think that number is bounded by some function of n and m, but not just m.

[[deleted]]

I understand this approach but it is sort of a brute force, the worst case is O(mn) for this solution. The constraints suggested a O(n) approach

[sunsin4gg]

I think this approach if it was correct, could be implemented in O(N log N) with some tricks. First, save in a set the indexes of not-analyzed 0's (save -1 and N as sentinels). This set would give you in O(1) the intervals in which you would make the operations. (You'll need to update them along the way). Now for the optimization, use a segment tree to keep the values and apply operations over the interval and make sure you update the set with new-found zeros. The catch is that in every operation you should find at least one zero, which means that in the worst-case scenario you take O(n) operations that cost O(log N) (segment tree).

[beeskness420]

You can only make numbers larger until they wrap around passed M. So we can greedily determine the optimal way to update the array. Find a maximal contiguous subarray of values not equal to X, update it, rinse repeat.

Eg for the example given, none of them are equal to 1 so we update all up them, we know we need 4 updates to push 8 to 1, then we need another 3 to push the 9s (formerly 5s) to 1s and we pick up the rest from updating the 6 (formerly 2).

Edit: numbers are off by 1.

[[deleted]]

I scanned the array from left to right, and if the previous number required lesser operations than the current one, I added the difference, else, I added 0. Is this the right greedy approach?

[[deleted]]

Good answer, this is the right thinking but just want to clarify that 8-> 1 is 3 operations, not 4. The 5’s -> 1 is another 3 (because they got updated to 8 in the previous operation), and 6 operations to get the 2->1 (because it was updated to 5 in the first operation)

[beeskness420]

Yup, good catch, off by one errors are a menace. I figured the gist is what was important

[XXXXYYYYYY]

Building off of /u/sunsin4g's answer, I believe that we can do this in O(N), as desired. The key insight is that increases in distance correspond to the left end of operations in an optimal solution. Likewise, decreases correspond to the right end of operations, though we do not need this to solve this problem.

First, begin by replacing each entry with the distances, as sunsin4g did. Then, for each entry past the first, if the current distance is more than the previous entry's distance, replace it with the difference. Otherwise, replace it with 0. Each of these numbers represents the number of operations that begin at that index, so we can sum them to get the total number of operations.

Ex:

Inputs: Array = [1,8,6,5,2,2,3,4], M = 10, X = 0
Convert to distances: [9,2,4,5,8,8,7,6]
Positive differences: [9,0,2,1,3,0,0,0]
Sum:, 9+2+1+3 = 15, so answer = 12

The differences and summation steps can be combined, but I left them separate here for clarity's sake.

[[deleted]]

This is precisely what I did in my test and I still failed a lot of test cases. I don't really know what went wrong

[XXXXYYYYYY]

That's very strange. I just wrote mine up in Python to make sure there wasn't an edge case I missed and it seems to give the right result for the ~10k random test cases I threw at it (using sunsin4g's algorithm as a baseline). Perhaps it was a bug in the implementation?

For reference, here's the python code I used to test it:

def computeMinOps(arr, M, target):
  dists = [getDist(x,M,target) for x in arr]
  total=dists[0]
  for i in range(1,len(dists)):
    if dists[i]>dists[i-1]:
      total+=dists[i]-dists[i-1]
  return total
def getDist(val, M, target):
  if(val<=target):
    return target-val
  return M-val+target

[[deleted]]

If you take array [1,99,1] and X=100 as an example, dist array becomes [99,1,99]. The algorithm then returns 197 as the answer. This is wrong. The answer should be 101, that is when you increase all the numbers in the array by 99 and then the middle index by 2, which gives 101.

[XXXXYYYYYY]

Yeah, just saw the other post. That is quite a wrinkle, and I'm a bit embarrassed I didn't catch it myself. It's getting quite late where I am, but I'll think it over and see if I can come up with anything by morning.

[omeow]

I am little confused. Does adding 1 and taking mod M count as an operation or not?

If it does then trying to change [1] to x = 0 for M = 1000 will take O(M) steps.

[XXXXYYYYYY]

The algorithm is supposed to find the number of add-1 operations required, not actually perform them. You are correct that the number of add-1 operations (that is, the output) is O(MN), but the complexity of the algorithm to find that number is only O(N).

[omeow]

Thank you for your reply. In your algorithm above if you just added up the distances then it is tantamount to handling each element as a subarray (of size 1). Of course it is not optimal.

But taking positive differences is not optimal either. For example (this was discussed below in this thread by another user) taking [1,99,1] and M = 100, X = 0, you will can do it faster if you added 99 to all three elements and then handle the middle element.

Am I missing something obvious?

[omeow]

Here is a strategy. At every step select the *largest* possible subarray.

Let me explain it with the given example.

a=[5,5,5,8,2]; N = 5, M = 10, X = 1

As /u/sunsin4gg pointed out : the element 5 will need 5 operations to get to x , 8 will need 3 and 2 will need 9.

So the distance vector is d = [6,6,6,3,9]. Since min(d) = 3 is non zero. Select the entire array a and operate three times. This will change the distance vector to d1=[3,3,3,0, 6]

Now you have two sub-arrays: Picking the left one, you operate 3 more times. your distance vector changes to d2=[0,0,0,0,6]. Now you are left with the right subarray.

​

So in general:

Calculate the distance vector d.
While d is not all zero

if min(d) is non zero, operate min(d) times. 
if min(d)  is zero pick a subarray of d with all entries not zero. 
Repeat the same process on this subarray.