Sponsored
Sponsored
Sort the array first. For each possible count of elements x, check if there are exactly x numbers in the array that are greater than or equal to x.
Time Complexity: O(n log n) due to sorting, followed by O(n) for checking, resulting in O(n log n). Space Complexity: O(1) additional space.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int specialArray(std::vector<int>& nums) {
6 std::sort(nums.begin(), nums.end());
7 int n = nums.size();
8 for (int x = 0; x <= n; ++x) {
9 int count = 0;
10 for (auto num : nums) {
11 if (num >= x) {
12 count++;
13 }
14 }
15 if (count == x) {
16 return x;
17 }
18 }
19 return -1;
20}
21
22int main() {
23 std::vector<int> nums = {0, 4, 3, 0, 4};
24 std::cout << specialArray(nums) << std::endl;
25 return 0;
26}
This C++ solution sorts the input vector and checks for each possible x, counting if there are exactly x numbers >= x.
Utilize binary search on the result potential values from 0 to nums.length to efficiently find the special x.
Time Complexity: O(n log n) due to sorting initially, and O(n log n) for the binary search with counting operations. Space Complexity: O(1) additional space.
1
This solution uses binary search over the number of potential special cases, reducing the search space for efficiency.