lundi 31 janvier 2022

Making an array equal by decreasing elements adjacent to each other

I was doing this exercise in my computer science class for a warm up earlier, which was to find the minimum number of moves to make all the elements in an array equal to each other, where the only operation is to subtract one from an element in an array.

This made me curious about extensions to the problem; for example I immediately thought of an extension, how many moves will it take to make all the elements in an array equal to each other, where the only operation is to subtract one from two elements that are adjacent to each other.

For example: Given array [4, 6, 4], we can decrease elements in index 0 and 1 to get [3, 5, 4], then [3, 4, 3], then [2, 3, 3], and then decrease elements in index 1 and 2 to get [2, 2, 2]. This would take 4 moves. However, how would we extend this kind of thinking to larger arrays, where we cannot trace this out by hand like I just did above?

Cheers

Aucun commentaire:

Enregistrer un commentaire