Using any programming language that supports functions, have the function
is_enough(strArr)
that take strArr
which will be an an array consisting of the following elements:
N
which will be the number of gas stations in a circular route- and each subsequent element will be the string
g:c
whereg
is the amount of gas in gallons at that gas station andc
will be the amount of gallons of gas needed to get to the following gas station.
For example strArr
may be:
["4","3:1","2:2","1:2","0:1"].
Your goal is to return the index of the starting gas station that will allow you to travel around the whole route once, otherwise return the string "impossible".
For the example above there are 4 gas stations, and your program should return the string "1" because:
Starting at station 1 you receive 3 gallons of gas and spend 1 getting to the next station.
Then you have 2 gallons + 2 more at the next station and you spend 2 so you have 2 gallons when you get to the 3rd station.
You then have 3 but you spend 2 getting to the final station,
At the final station you receive 0 gallons and you spend your final gallon getting to your starting point.
Starting at any other gas station would make getting around the route impossible, so the answer is "1".
If there are multiple gas stations that are possible to start at, return the smallest index (of the gas station). N
will be >= 2
.
Correct Sample Outputs:
Input: ["4","1:1","2:2","1:2","0:1"]
Output: "impossible"
Input: ["4","0:1","2:2","1:2","3:1"]
Output: "4"
The winner will be the one to use the shortest code although it will be long.
N+1
elements instrArr
? This would makeN
redundant in case the language already provides a way of getting the length of the array, right? (it'd still be useful for e.g. C though.) \$\endgroup\$ – FireFly Feb 4 '14 at 18:45is_enough
(9 chars); three are using a single-char name, and one doesn't name the function at all. Could you please clarify what is permissible? \$\endgroup\$ – Peter Taylor Feb 4 '14 at 23:28