Monday, September 11, 2017

Number of jumps for a thief to cross walls?


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: