Discover the Array factor left after alternate removing of minimal and most


View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given an array Arr of size N, it’s lowered by 1 factor at every step. Most and Minimal components will probably be eliminated in alternating order from the remaining array till a single factor is remaining within the array. The duty is to search 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 beneath concept to resolve the issue:

The thought is to type the array and return the center factor as the entire proper and left components will probably be eliminated within the course of.

Observe the beneath steps to resolve this drawback:

  • 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++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int lastRemaining(int arr[], int N)

{

    

    if (N == 1)

        return arr[0];

  

    

    type(arr, arr + N);

  

    

    return arr[(N - 1) / 2];

}

  

int essential()

{

    int arr[] = { 1, 5, 4, 2 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    cout << lastRemaining(arr, N) << endl;

    return 0;

}

Time Complexity: O(N * log(N)), for sorting the given array of measurement N.
Auxiliary House: O(1), as fixed additional area is required.

Leave a Reply