New update is available. Click here to update.

Avoiding traps

PROBLEM STATEMENT

Given an array of 'N' elements 'OBSTACLES', where each element represents the coordinate of the obstacle on a straight line. We start jumping from point 0 and we need to reach the end of the line avoiding all the obstacles which are present on the line. The length of every jump should be the same. For example, if we jump from 0 to 3, the jump is of 3 units hence the next jump should also be of 3 units that is from 3 to 6 and so on.

Find the minimum length of the jump so that we can reach the end of the line avoiding all obstacles.

Note:

1.The end will be a minimum possible coordinate, greater than the maximum element in the given array of elements.

2.Avoiding obstacles means that we cannot stop at the given coordinates.

3.The elements may not be in sorted order.

4.The last jump can be of any unit, provided it crosses the endpoint.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2 * T lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘N’, denoting the number of obstacles on the straight line.

The second line of each test case contains an array 'OBSTACLES' of 'N' elements, denoting the obstacles on the straight line.

Output format:

For each test case, print a single line containing a single integer denoting the minimum length of the jump to reach the end, avoiding all the obstacles.

The output of each test case will be printed in a separate line.

Note

You don't have to print anything. It has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 50
1 <= N <= 1000
1 <= OBSTACLES[i] <= 10 ^ 6

Where ‘T’ is the total number of test cases, ‘N’ denotes the number of obstacles on the straight line, and ‘OBSTACLES[i]’ denotes the coordinates of obstacles on the straight line.

Time limit: 1 sec.

Approach 1

Find the largest element in the array of elements and store it in variable ‘maxElement’.
Create a boolean vector, ‘B’ of size equal to the value of the largest element in vector ‘A’. Initialize the vector ‘B’ with value ‘false’.
Considering the elements of vector ‘A’ as an index in vector ‘B’, mark these indexes as ‘true’.
Run a loop where ‘i’ ranges from ‘1’ to ’maxElement’.
A. Consider ‘i’ as the possible length of the jump.
B. Initialize a boolean variable flag to ‘false’.
C. For every ‘i’, run a loop where ‘j’ ranges from ‘i’ to ’maxElement’. ‘j’ stores the multiple of ‘i’. So, after every iteration, increment ‘j’ with value ‘i’.
a. Check whether the current multiple i.e, ‘j’ is present in the vector ‘B’ or not.
b. If it is present, it means that the length of the jump, ‘i’ will touch the obstacle ‘j’. Hence, break the loop, as ‘i’ is not the possible length of jump and turn the boolean variable flag to true.
If for length ‘i’, the value of the flag is ‘false’ after the completion of the ‘j’ loop, it means ‘i’ did not hit any obstacle and is the required answer.
Finally, return ‘i’.
If the answer is greater than ’maxElement’, then after completing all the loops, we return ’maxElement+1’.

Try Problem

Approach 2

Take a variable ‘jumpLength’ and initialize it to 1. Let another boolean variable be ‘obstacleHit’ and initialize it to ‘true’.

Run a while loop till the value of ‘obstacleHit’ is ‘true’.

On entering the while loop, increment the value of ‘jumpLength’. ‘jumpLength’ is the length of jump which is considered.
Turn ‘obstacleHit’ to ‘false’ assuming ‘jumpLength’ to be the required result.
Run a loop, iterating all the elements of vector ‘A’.
a. If the element is divisible by ‘jumpLength’, it means with the current length of the jump, the obstacle will get hit. So, we discard the ‘jumpLength’ and break the loop, so that further elements are not traversed. Turn ‘obstacleHit’ to ‘true’ so that while loop continues with the incremented value of ‘jumpLength’.
b. Else, keep iterating the vector ‘A’.
Once all the elements of vector ‘A’ are not divisible by a particular value of ‘jumpLength’, the while loop ends indicating that ‘jumpLength’ is the required answer as it does not hit any obstacle.
Lastly, return ‘jumpLength’ which is the minimum length of a jump to reach the end.

Try Problem