Moving Stones Until Consecutive Leetcode Solution

Problem Statement

In this problem, we are given three stones at positions a, b and c. We have to make them consecutive by performing the following step one or more times.

In each step, We will pick a left stone or a right stone and put somewhere in the between the range of left to right stone.

Let's under stand this better by following picture:

 

We have to answer both the minimum and maximum number of such steps to make these stones consecutive.

Example

a = 1, b = 2, c = 5

 

Explanation: Move the stone from 5 to 3, or move the stone from 5 to 4 to 3.

a = 4, b = 3, c = 2

 

We cannot make any moves.

a = 3, b = 5, c = 1

 

Move the stone from 1 to 4; or move the stone from 1 to 2 to 4.

Approach

First let's talk about how to calculate maximum steps. Can't we simply say that the number of moves will be maximum only when both the stones at extremes come closer to middle stone by 1 unit.

Thus the number of positions between left stone and mid stone + the number of position between mid stone and right stone will be our maximum number of steps to make them consecutive.

 

Now the main problem is how to calculate minimum number of steps. We can find out minimum by understanding the following conditions.

Let's call number of positions between left stone and mid stone is lspace and the number of positions between mid stone and right stone is rspace.

Only one of the following 4 situation can be said about the initial position of these stones.

 

1.

 

www.tutorialcup.com/leetcode-solutions/moving-stones-unti...

Done