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

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.

Examples :

```Input  : [7, 3, 16, 10]
Output : 3
Number of integers greater than 3
is three.

Input  : [-1, -9, -2, -78, 0]
Output : 0
Number of integers greater than 0
is zero.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Method 1 (Brute Force)
Iterate through the array. For every element arr[i], find the number of elements greater than arr[i].

## CPP

 `// C++ program to find Noble elements ` `// in an array. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns a Noble integer if present, ` `// else returns -1. ` `int` `nobleInteger(``int` `arr[], ``int` `size) ` `{ ` `    ``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; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {10, 3, 20, 40, 2}; ` `    ``int` `size = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``int` `res = nobleInteger(arr, size); ` `     `  `    ``if` `(res != -1) ` `        ``cout<<``"The noble integer is "``<< res; ` `    ``else` `        ``cout<<``"No Noble Integer Found"``; ` `} ` ` `  `// This code is contributed by Smitha. `

## Java

 `// Java program to find Noble elements ` `// in an array. ` `import` `java.util.ArrayList; ` ` `  `class` `GFG { ` `     `  `    ``// Returns a Noble integer if present, ` `    ``// else returns -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``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `[] arr = {``10``, ``3``, ``20``, ``40``, ``2``}; ` `        ``int` `res = nobleInteger(arr); ` `        ``if` `(res != -``1``) ` `            ``System.out.println(``"The noble "` `                     ``+ ``"integer is "``+ res); ` `        ``else` `            ``System.out.println(``"No Noble "` `                        ``+ ``"Integer Found"``); ` `    ``} ` `} `

## Python3

 `# Python3 program to find Noble ` `# elements in an array. ` ` `  `# Returns a Noble integer if ` `# present, else returns -1. ` `def` `nobleInteger(arr, size): ` ` `  `    ``for` `i ``in` `range``(``0``, size): ` `     `  `        ``count ``=` `0` `        ``for` `j ``in` `range``(``0``, size): ` `            ``if` `(arr[i] < arr[j]): ` `                ``count ``+``=` `1` `        ``# If count of greater  ` `        ``# elements is equal ` `        ``# to arr[i] ` `        ``if` `(count ``=``=` `arr[i]): ` `            ``return` `arr[i] ` `     `  `    ``return` `-``1` ` `  `# Driver code ` `arr ``=` `[``10``, ``3``, ``20``, ``40``, ``2``] ` `size ``=` `len``(arr) ` `res ``=` `nobleInteger(arr,size) ` `if` `(res !``=` `-``1``):  ` `    ``print``(``"The noble integer is "``, ` `                              ``res) ` `else``: ` `    ``print``(``"No Noble Integer Found"``) ` ` `  `# This code is contributed by ` `# Smitha. `

## C#

 `// C# program to find Noble elements ` `// in an array. ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns a Noble integer if present, ` `    ``// else returns -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; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[] arr = {10, 3, 20, 40, 2}; ` `        ``int` `res = nobleInteger(arr); ` `        ``if` `(res != -1) ` `            ``Console.Write(``"The noble integer"` `                              ``+ ``" is "``+ res); ` `        ``else` `            ``Console.Write(``"No Noble Integer"` `                                 ``+ ``" Found"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Smitha. `

## PHP

 ` `

Output :

`The noble integer is 3`

Method 2 (Use Sorting)

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).

Note: Array may have duplicate elements. So, we should skip the elements (adjacent elements in the sorted array) that are same.

## C++

 `// C++ program to find Noble elements ` `// in an array. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns a Noble integer if present, ` `// else returns -1. ` `int` `nobleInteger(``int` `arr[], ``int` `n) ` `{ ` `    ``sort(arr, arr + n); ` ` `  `    ``// Return a Noble element if present ` `    ``// before last. ` `    ``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; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {10, 3, 20, 40, 2}; ` `    ``int` `res = nobleInteger(arr, 5); ` `    ``if` `(res != -1) ` `        ``cout << ``"The noble integer is "` `<< res; ` `    ``else` `        ``cout << ``"No Noble Integer Found"``; ` `    ``return` `0; ` `} ` ` `  `// This code is contributed by Rajput-Ji `

## Java

 `// Java program to find Noble elements ` `// in an array. ` `import` `java.util.Arrays; ` ` `  `public` `class` `Main ` `{ ` `    ``// Returns a Noble integer if present, ` `    ``// else returns -1. ` `    ``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

## Python

 `# Python3 code to find Noble elements ` `# in an array ` ` `  `def` `nobleInteger(arr): ` `     `  `    ``arr.sort() ` `     `  `    ``# Return a Noble element if  ` `    ``# present before last ` `    ``n ``=` `len``(arr) ` `     `  `    ``for` `i ``in` `range``(n ``-` `1``): ` `         `  `        ``if` `arr[i] ``=``=` `arr[i ``+` `1``]: ` `            ``continue` `             `  `        ``# In case of duplicates we reach ` `        ``# last occurence here ` `        ``if` `arr[i] ``=``=` `n ``-` `i ``-` `1``: ` `            ``return` `arr[i] ` `     `  `    ``if` `arr[n ``-` `1``] ``=``=` `0``: ` `        ``return` `arr[n ``-` `1``] ` `    ``return` `-``1` ` `  `# Driver code ` `arr ``=` `[``10``, ``3``, ``20``, ``40``, ``2``] ` ` `  `res ``=` `nobleInteger(arr) ` ` `  `if` `res !``=` `-``1``: ` `    ``print``(``"The noble integer is"``, res) ` `else``: ` `    ``print``(``"No Noble Intger Found"``) ` ` `  `# This code is contributed ` `# by Mohit Kumar `

## C#

 `// C# program to find Noble elements ` `// in an array.  ` `using` `System; ` ` `  `public` `class` `GFG { ` `     `  `    ``public` `static` `int` `nobleInteger(``int``[] arr) ` `    ``{ ` `        ``Array.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; ` `    ``} ` `     `  `    ``// Driver code ` `    ``static` `public` `void` `Main () ` `    ``{ ` `        ``int` `[] arr = {10, 3, 20, 40, 2}; ` `        ``int` `res = nobleInteger(arr); ` `        ``if` `(res != -1) ` `        ``Console.Write(``"The noble integer is "` `                                      ``+ res); ` `        ``else` `            ``Console.Write(``"No Noble Integer "`  `                                  ``+ ``"Found"``); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by Shrikant13. `

## PHP

 ` `

Output :

```The noble integer is 3.
```