## Thursday, April 20, 2017

### Noble integers in an array (count of greater elements is equal to value) - GeeksforGeeks

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.

1. Sort the Array arr[] in ascending order. This step takes (O(nlogn)).
2. 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``;`
`    ``}`
Read full article from Noble integers in an array (count of greater elements is equal to value) - GeeksforGeeks