Given an array Arr of size N, it’s diminished by 1 factor at every step. Most and Minimal parts might be eliminated in alternating order from the remaining array till a single factor is remaining within the array. The duty is to seek out the remaining factor within the given array.
Examples:
Enter: arr[] = {1, 5, 4, 2}
Output: 2
Rationalization:
Take away Max factor i.e., 5 arr[] = {1, 4, 2}
Take away Min factor i.e., 1 arr[] = {4, 2}
Take away Max factor i.e., 4 arr[] = {2}Enter: arr[] = {5, 10}
Output: 5
Strategy:
Observe the under concept to resolve the issue:
The thought is to kind the array and return the center factor as all the proper and left parts might be eliminated within the course of.
Observe the under steps to resolve this downside:
- If N =1, return arr[0]
- Type the array arr[]
- Return the center factor of the array i.e., arr[(N-1)/2]
Under is the implementation of the above strategy:
C++
|
|
Time Complexity: O(N * log(N)), for sorting the given array of measurement N.
Auxiliary House: O(1), as fixed additional house is required.
