Avoiding traps

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.

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.

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.

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.

Obstacles are at positions 5, 3, 6, 7, 9. If we take a jump of size 1, it will touch 3 and so it is not viable For jump size 2, it will touch 6 and so it is discarded. For jump size 3, it will touch 3 and so it is also discarded. For jump size 4, we will jump from 0 to 4, then 4 to 8, then 8 to 12. Hence, we reach the end by avoiding all the obstacles. Test case 2: Obstacles are at positions 5, 8, 9, 13, 14. With jump size 6, we will jump from 0 to 6, then 6 to 12, followed by 12 to 18. Hence, we reach the end by avoiding all the obstacles.

Brute force

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’.

Time Complexity

O(maxElement * log(maxElement)), ‘maxElement’ is the largest element in the given array of elements.

In the worst case, the minimum length of a jump will be ‘maxElement + 1’. So, we are considering all jumps from 1 to ‘maxElement + 1’. For each jump length ‘i’, the number of jump points we are checking for obstacles is ‘maxElement + 1’ / i. So, the time complexity becomes ‘maxElement + 1’ / 1 + ‘maxElement + 1’ / 2 + … + 1. Hence, the overall complexity becomes O(maxElement * log(maxElement)).

Space Complexity

O(maxElement), where ‘maxElement’ is the largest element in the given array of elements.

In the worst case, we will be using O(maxElement) space, therefore net space complexity will be O(maxElement).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of sample input 1:

Sample Input 2:

Sample Output 2: