Noble integers in an array (count of greater elements is equal to value) - GeeksforGeeks
Given an array arr[], find a Noble integer in it. An integer x is said to be Noble in arr[] if the number of integers greater than x are equal to x. If there are many Noble integers, return any of them. If there is no, then return -1.
Read full article from Noble integers in an array (count of greater elements is equal to value) - GeeksforGeeks
Given an array arr[], find a Noble integer in it. An integer x is said to be Noble in arr[] if the number of integers greater than x are equal to x. If there are many Noble integers, return any of them. If there is no, then return -1.
- Sort the Array arr[] in ascending order. This step takes (O(nlogn)).
- Iterate through the array. Compare the value of index i to the number of elements after index i. If arr[i] equals the number of elements after arr[i], it is a noble Integer. Condition to check: (A[i] == length-i-1). This step takes O(n).
public static int nobleInteger(int arr[]) { Arrays.sort(arr); // Return a Noble element if present // before last. int n = arr.length; for (int i=0; i<n-1; i++) { if (arr[i] == arr[i+1]) continue; // In case of duplicates, we // reach last occurrence here. if (arr[i] == n-i-1) return arr[i]; } if (arr[n-1] == 0) return arr[n-1]; return -1; } public static int nobleInteger(int arr[]) { int size = arr.length; for (int i=0; i<size; i++ ) { int count = 0; for (int j=0; j<size; j++) if (arr[i] < arr[j]) count++; // If count of greater elements is equal // to arr[i] if (count == arr[i]) return arr[i]; } return -1; }