Noble integers in an array or count of greater elements is equal to value java

Noble integers in an array or count of greater elements is equal to value?.

Explanation:

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.

Solution:

There can be many approach to solve this problem.you can solve this problem by "Brute Force" approach and also by
"Sorting" .

Brute Force Approach:

First Step: Iterate through the array.
Second Step: For every element arr[i], find the number of elements greater than arr[i].

Sample Program:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class NobleIntegerApp
{

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");
}

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 == arr[i])
                return arr[i];
        }
        return -1;
    }

}

 Output:The noble integer is 3

Complexity: Though this is not very good Solution as you can see there are two loops and comparison happening.

Sorting Approach:

Step one: Sort the array in ascending order.complexity O(nlogn).
Step two:Iterate through the array.
Step three: 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.

Step four:Check condition, (A[i] == length-i-1). the complexity in doing this would be O(n).

Sample Code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class NobleIntegerApp
{

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");
}

public static int nobleInteger(int arr[])
      {
 Arrays.sort(arr);
       int n = arr.length;
       for (int i=0; i<n-1; i++)
       {
           if (arr[i] == arr[i+1])
               continue;

           if (arr[i] == n-i-1)
               return arr[i];
       }

       if (arr[n-1] == 0)
           return arr[n-1];

       return -1;
    }

}


Output: The noble integer is 3