There are N cars (numbered 1 through N) on a circular track with length .Foreachi(2<i<N), the i-th of them is at a distance i -- I clockwise from car 1,Le. car 1 needs to travel a distance 1 — 1 clockwise to reach car i. Also, for each valid i, the i-th car has f litres of gasoline in it initialy
You are driving car I in the clockwise direction. To move one unit of distance in this direction, you need to spend 1 litre of gasoline. When you pass another car (even if you'd run out of gasoline exactly at that point), you steal all its gasoline. Once you do not have any gasohne left, you stop.
What is the total clockwisedistance travelled by your car? write a c program
Answers
think pkm made a unstated assumption that only the car adjacent to empty space can be moved, which is not stated in the problem. Problem actually says moving only one car at a time into the spot but does not say anything about adjacency.
So I would think that the parking lot can be represented using a simple array such as below:
Initial configuration: 1 5 7 3 9 _ 2 4 6 8
Expected configuration: 1 4 5 2 3 6 9 _ 7 8
Solution: 1 is already placed in appropriate position let us move to second position where 4 should be placed so move 5, from the second place in the initial configuration to empty space and bring 4 in the second place, which is the expected configuration. So you will be performing one comparison and two swapping operations for every car to reach its final configuration hence
Complexity is O(3n) = O(n)