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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int specialArray(int* nums, int numsSize) {
9 qsort(nums, numsSize, sizeof(int), compare);
10 for (int x = 0; x <= numsSize; x++) {
11 int count = 0;
12 for (int i = 0; i < numsSize; i++) {
13 if (nums[i] >= x) {
14 count++;
15 }
16 }
17 if (count == x) {
18 return x;
19 }
20 }
21 return -1;
22}
23
24int main() {
25 int nums[] = {0, 4, 3, 0, 4};
26 int numsSize = sizeof(nums) / sizeof(nums[0]);
27 int result = specialArray(nums, numsSize);
28 printf("%d\n", result);
29 return 0;
30}
This C program sorts the input array and then iterates to determine if the number of elements greater than or equal to x is exactly 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 Java code uses binary search in a sorted array to find the x such that the count of numbers >= x is equivalent to x.