Ninja’s Challenge

Moderate

0/80

6 upvotes

Asked in companies

Problem statement

There is a list ‘ARR’ of ‘N’ sorted numbers. Ninja’s friend wants to challenge Ninja’s mental ability. So, he thought to rotate the given sorted list at a random pivot. Now, he challenges Ninja to find the minimum number of ‘ARR’ in minimum time. Can you help Ninja with this challenge?

You are given a rotated sorted array ‘ARR’ having ‘N’ elements. Your task is to return the minimum number present in array ‘ARR’.

For Example

If the ARR is [4,6,9,11,1,2,2] ,the minimum number is 1.Hence the answer is 1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N’, denoting the number of elements in array ‘ARR’.

The following line contains ‘N’ values corresponding to elements of ‘ARR’.

Output Format:

For each test case, print the minimum number present in ‘ARR’.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^7.
1 <=ARR[i] <=10^6.

Time limit: 1 sec

Sample Input 1:

2
7 
4 6 9 11 1 2 2
5 
4 5 2 2 4

Sample Output 1:

1
2

Explanation of sample input 1:

For the first test case,

The minimum value present in ‘ARR’ is 1. Hence, the answer is 1.

For the second test case:

The minimum value present in ‘ARR’ is 1. Hence, the answer is 2.

Sample Input 2:

2
8 
9 9 9 10 2 3 6 6 
6 
4 6 7 9 2 4

Sample Output 2:

2
2

Hint 1

Hint 2

Check the whole array.

Approaches (2)

Approach 1

Approach 2

Brute Force using Linear Search.

In this approach, we will simply iterate over the whole array and try to find the minimum number.

Algorithm:

Set ‘ANS’ as ARR[0].
For i in range 1 to ‘N’ -1, do the following:
- Set ‘ANS’ as the minimum of ‘ANS’ and ‘ARR’[i].
Return ‘ANS’.

Time Complexity

O(N), where ‘N’ is the number of elements in array ‘ARR’.

In this approach, we iterate the whole array and compare the ‘ANS’ with every element, which takes N comparisons in the worst case. Hence, the overall time complexity is O(N).

Space Complexity

O(1).

In this approach, we are using constant space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Ninja’s Challenge

Console