Last Updated: 28 Oct, 2021

Ninja’s Challenge

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

In this approach, we will use a modified binary search over the array. In every step, we will divide the array into two parts. And will decide which part is sorted and move to the half in which the minimum element will lie. We will always move to the half where the pivot point is present.

Conditions will be:

1. If ARR[mid] >= ARR[R], the right half is not sorted, the pivot point will lie in the right half, move to the right half.

2. Else, Move to the left half.

But, as the array may contain duplicate elements, these conditions do not guarantee that the respective half is sorted.

For example, if the ARR is [3 1 2 3 3 3 3] and mid=3,l=0 and r=6.The condition ARR[l]<=ARR[mid] is satisfied but the left half is not sorted.

So, we have to deal with the duplicate numbers separately as the following:

1. If A[r] == A[mid],decrement r to r-1.

So, according to all these conditions, we will make a binary search approach, which will find the minimum element of the ‘ARR’.

Algorithm:

Set ‘L’ as 0.
Set ‘R’ as ‘N’ -1.
While ‘L’ < ‘R’, do the following:
- Set ‘MID’ as (‘L’+’R’)/2.
- If ARR[‘MID’] is equal to ARR[‘R’] :
  - Decrement ‘R’ to ‘R’-1.
  - Continue.
- If ‘ARR’[‘MID’] >= ‘ARR[‘R’]’:
  - Move to the right half.
  - Set ‘L’ to ‘MID’+1.
- Else:
  - Move to the left half.
  - Set ‘R’ to ‘MID’.
‘ARR’[‘R’] is the minimum element of the array.
Return ‘ARR’[‘R’].

Solve now