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)
- 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).
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.
leave a comment
0 Comments