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)
- Input array from user having n elements.
- Pick up elements one by one and count greater elements.
- 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)
- Input array from user having n elements.
- Sort the array in increasing order.
- 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