Number of jumps for a thief to cross walls?.
A thief trying to escape from a jail. He has to cross N walls each with varying heights (every height is greater than 0). He climbs X feet every time. But, due to the slippery nature of those walls, every time he slips back by Y feet. Now the task is to calculate the total number of jumps required to cross all walls and escape from the jail.
Examples:
Input : heights[] = {11, 11}
X = 10;
Y = 1;
Output : 4
He needs to make 2 jumps for first wall
and 2 jumps for second wall.
Input : heights[] = {11, 10, 10, 9}
X = 10;
Y = 1;
Output : 5
Sample Code:
public class Test
{
static int jumpcount(int x, int y, int n, int height[])
{
int jumps = 0;
for (int i = 0; i < n; i++)
{
// Since all heights are
// greater than 1, at-least
// one jump is always required
jumps++;
// More jumps required if height
// is greater than x.
if (height[i] > x)
{
// Since we have already counted
// one jump
int h = height[i] - (x - y);
// Remaining jumps
jumps += h/(x - y);
// If there was a remainder greater
// than 1. 1 is there to handle cases
// like x = 11, y = 1, height[i] = 21.
if (h % (x-y) > 1)
jumps++;
}
}
return jumps;
}
public static void main(String args[])
{
int x = 10;
int y = 1;
int height[] = { 11, 34, 27, 9 };
int n = height.length;
System.out.println(jumpcount(x, y, n, height));
}
}
Output: 10
No comments:
Post a Comment