HashedIn | OA | Max Hops
Anonymous User
1006

There are n rabbits on a straight line of infinite length. The x coordinate and hop distance h of each rabbit is given in ascending order of x. A rabbit can either hop to x + h or x - h only if the new position is not occupied. Find the maximum number of rabbits that can hop at once.

Example:

Input: n = 5, x = [1,2,5,10,19], h = [2,1,15,9,1]
Output: 3

Explanation:

1 -> 3
2 -> No as 1 was occupied and 3 is occupied
5 -> 20
10 -> No as 1 and 19 are occupied
19 -> 18

Negative x coordinate is not allowed

The question was not well explained in the OA, so this is what I have understood.

The output would be 4 if negative coordinates were allowed.

How to solve with and without the negative x coordinate constraint?

Comments (9)