Tutorialspoint.dev

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.



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 <bits/stdc++.h>
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

<?php
// PHP program to find Noble 
// elements in an array.
  
// Returns a Noble integer 
// if present, else returns -1.
function nobleInteger( $arr, $size)
{
    for ( $i = 0; $i < $size; $i++ )
    {
        $count = 0;
        for ( $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
$arr = array(10, 3, 20, 40, 2);
$size = count($arr);
$res = nobleInteger($arr, $size);
  
if ($res != -1)
    echo "The noble integer is ", $res;
else
    echo "No Noble Integer Found";
  
// This code is contributed by anuj_67..
?>


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<bits/stdc++.h>
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<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
    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");
    }
}

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

<?php
// PHP program to find Noble elements
  
// Returns a Noble integer if present,
// else returns -1.
function nobleInteger( $arr)
    {
        sort($arr);
  
        // Return a Noble element if 
        // present before last.
        $n = count($arr);
        for ( $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
    $arr = array(10, 3, 20, 40, 2);
    $res = nobleInteger($arr);
    if ($res != -1)
        echo "The noble integer is ", $res;
    else
        echo "No Noble Integer Found";
  
// This code is contributed by anuj_67.
?>


Output :

The noble integer is 3.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter