Monday, September 12, 2022
HomeWordPress DevelopmentDiscover the Array aspect left after alternate removing of minimal and most

Discover the Array aspect 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 diminished by 1 aspect at every step. Most and Minimal parts can be eliminated in alternating order from the remaining array till a single aspect is remaining within the array. The duty is to search out the remaining aspect within the given array.

Examples:

Enter: arr[] = {1, 5, 4, 2}
Output: 2
Clarification
Take away Max aspect i.e., 5 arr[] = {1, 4, 2}
Take away Min aspect i.e., 1 arr[] = {4, 2}
Take away Max aspect i.e., 4 arr[] = {2}

Enter: arr[] = {5, 10}
Output: 5

Strategy:

Observe the under concept to resolve the issue:

The thought is to type the array and return the center aspect as the entire proper and left parts can be eliminated within the course of.

Observe the under steps to resolve this downside:

  • If N =1, return arr[0]
  • Kind the array arr[]
  • Return the center aspect of the array i.e., arr[(N-1)/2]

Under is the implementation of the above method:

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 principal()

{

    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 dimension N.
Auxiliary House: O(1), as fixed further house is required.

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments