Bridge and Torch Puzzle

Given an array of positive distinct integer denoting the crossing time of ’n’ people. These ’n’ people are standing at one side of bridge. Bridge can hold at max two people at a time. When two people cross the bridge, they should have a light torch at all times. There is only one light torch. Find the minimum total time in which all persons can cross the bridge.given array: {1,3,6,8,12} and total minimum time would be 27.

  • two people would have to travel to the other side and make sure one comes back and if fastest comes back that would contribute to a lesser time
  • The time taken by two people would be the time of the slowest among two since the fastest person has to match the speed with slowest
  • Assume the two sides one to be the dangerous side and the other the safe side. The minimum time is taken when people in dangerous has less time to wait for
  • that is there should always be at least one fastest candidates on the both the safe side to make sure he comes back to rescue people from danger fast to hand out the torch
  • sort the array first to array ordered in terms of speed
  • when there are only 2 people or less and they can directly travel to safe side and would not have to return, so a[n-1] that is the slowest time would be total time and the minimum time
  • when number of people is exactly 3 all of the people’s speed would contribute to the time
  • when number of people is greater than 3, we see a pattern a[1],a[0],a[n-1],a[1] time taken for a sorted sequence and we calculate time based on this pattern and use recursion for the same.
public static int fun(int a[],int n)
{
int result=0;
if(n<3){
result=a[n-1];
}
else if(n==3){
result=a[0]+a[1]+a[2];
}
else{
result+=a[1]+a[0]+a[n-1]+a[1]+fun(a,n-2);
}
return result;
}
  • the method fun is called n-2 time before reaching the base case and hence O(n-2) would contribute to O(n) time complexity and O(1) space complexity

Intimidated developer trying to find her way into technology dominant world