fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int getNumberOfDistinctElements(vector<int> &arr) {
  6. 	int n = arr.size();
  7. 	if(n <= 0) return 0;
  8.  
  9. 	int numberOfDistinctElements = 1;
  10. 	int currentElement = arr[0];
  11.  
  12. 	for(int i = 0; i < n; i++) {
  13. 		if(arr[i] != currentElement) {
  14. 			numberOfDistinctElements++;
  15. 			currentElement = arr[i];
  16. 		}
  17. 	}
  18.  
  19. 	return numberOfDistinctElements;
  20. }
  21.  
  22. int getUpperBound(vector<int> &arr, int target) {
  23. 	int n = arr.size();
  24. 	int low = 0, high = n-1;
  25. 	int upperBound = high;
  26.  
  27. 	while(low <= high) {
  28. 		int mid = low + (high - low) / 2;
  29.  
  30. 		if(arr[mid] >= target) {
  31. 			upperBound = mid;
  32. 			high = mid - 1;
  33. 		} else {
  34. 			low = mid + 1;
  35. 		}
  36. 	}
  37.  
  38. 	return arr[upperBound];
  39. }
  40.  
  41. int solve(vector<int> &arr) {
  42.     sort(arr.begin(), arr.end());
  43.  
  44.     int numberOfDistinctElements = getNumberOfDistinctElements(arr);
  45.     int upperBound = getUpperBound(arr, numberOfDistinctElements);
  46.  
  47.     return upperBound;
  48. }
  49.  
  50. int main() {
  51.     int numberOfTestCases;
  52.     cin >> numberOfTestCases;
  53.  
  54.     vector<int> results;
  55.  
  56.     while(numberOfTestCases--) {
  57.         int n;
  58.         cin >> n;
  59.  
  60.         vector<int> arr(n);
  61.  
  62.         for(int i = 0; i < n; i++) {
  63.             cin >> arr[i];
  64.         }
  65.  
  66.         results.push_back(solve(arr));
  67.     }
  68.  
  69.     for(const int result : results) {
  70.         cout << result << "\n";
  71.     }
  72. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
6
1 1 1 1 1 1
1
1000
5
8 10 15 20 25
8
2 5 2 4 1 2 5 3
6
40 4 1 95 8 40
stdout
copy 
1
1000
8
5
8
https://ideone.com/Wabt9I
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!