RUN


C++ program to find all elements in an array of integers that have at-least two greater elements.

Given: An array of n elements, we have to find all elements in the array which have at-least two greater elements than themselves.

Example:

Input: arr[] = { 15, 2, 20, 12, 40} 

Output: 15, 2, 12

Input: arr[] = { -2, 9, 12, -7, 2, 10}  
Output: -2, 9, -7, 2

# Brute Force (using loops)

  1. Input array from user having n elements. 
  2. Pick up elements one by one and count greater elements.
  3. If count > 2, then print that element.

Code:

#include<bits/stdc++.h>

using namespace std;

//finds elements having at-least two greater elements

void greater_elements(int arr[], int n){
  cout << "\nElements which have at-least two greater elements are: ";

  for (int i = 0; i < n; i++){
    int
    var = 0;

    for (int j = 0; j < n; j++)

      if (arr[j] > arr[i])

        var ++;

    if (var >= 2)

      cout << arr[i] << " ";

  }

}

int main(){

  int arr[100], n, i;

  cout << "Enter number of elements: ";

  cin >> n;

  cout << "\nEnter elements: ";

  for (i = 0; i < n; i++)

    cin >> arr[i];

  cout << "Elements are: ";

  for (i = 0; i < n; i++)

    cout << arr[i] << " ";

  greater_elements(arr, n);

  return 0;

}

Time Complexity : O(n2)

# Optimized Approach(using sorting)

  1. Input array from user having n elements. 
  2. Sort the array in increasing order.
  3.  Print first n-2 elements.

Code:

#include<bits/stdc++.h>

using namespace std;

void greater_elements(int arr[], int n){

  sort(arr, arr + n);

  for (int i = 0; i < n - 2; i++)

    cout << "\n" << arr[i] << " ";

}

// Driver Code 

int main(){

  int arr[100], n, i;

  cout << "Enter number of elements: ";

  cin >> n;

  cout << "\nEnter elements: ";

  for (i = 0; i < n; i++)

    cin >> arr[i];

  cout << "\nElements are: ";

  for (i = 0; i < n; i++)

    cout << arr[i] << ", ";

  cout << endl;

  greater_elements(arr, n);

  return 0;

}

Time Complexity : O(n Log n)

Report Error/ Suggestion

Related Posts:




CopyRight © 2020

CopyRight © 2020