Given an array arr[] consisting of N integers and an integer K, the task is to find the count of array elements having rank at most K.
Equal array elements will have equal ranks. Any array element numerically smaller than its immediate greater array element will be ranked one greater than the total number of array elements greater than it.
Examples:
Input: N = 4, arr[] = {100, 50, 50, 25}, K = 3
Output: 3
Explanation: Rank of the players will be {1, 2, 2, 4}.
There are 3 array elements whose ranks are less than or equal to 3.
Therefore, the answer is 3.Input: N = 5, arr[] = {2, 2, 3, 4, 5}, K = 4
Output: 5
Explanation: Rank of the players will be {4, 4, 3, 2, 1}.
There are 5 array elements whose ranks are less than or equal to 4.
Therefore, the answer is 5.
Naive Approach: The simplest approach is to find the current maximum element in the array and compare it with the previous maximum element. If they are equal, then the rank of the previous element and the current element must be equal. Otherwise, assign the rank of the current maximum element as one greater than the number of maximums obtained previously. Repeat this until the given array becomes empty or the rank becomes greater than K, whichever is earlier. After traversing, print the total number of deleted elements.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The idea is to use the Sorting Algorithm. After sorting the given array in non-increasing order and for each element, if the current and previous element is unequal, then the rank of the current element must be one greater than the previous element. Otherwise, it stays the same as that of the previous one. Follow the steps below to solve the problem:
- Sort the given arr[] in ascending order.
- Initialize variable rank and position with 1 to store the rank and the position of the current array element respectively.
- Traverse the sorted array from i = (N – 1) to 0 and perform the following operations:
- Update rank with position when adjacent array elements is not equal or when i is equal to (N – 1).
- Return position – 1 if rank becomes greater than K.
- Increment position in each traversal.
- Print N, if all the array elements have ranks not exceeding K.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h>using namespace std;// Function to find count of array// elements with rank less than or// equal to kint rankLessThanK(int* arr, int k, int n){ // Initialize rank and position int rank = 1; int position = 1; // Sort the given array sort(arr, arr + n); // Traverse array from right to left for(int i = n - 1; i >= 0; i--) { // Update rank with position, if // adjacent elements are unequal if (i == n - 1 || arr[i] != arr[i + 1]) { rank = position; // Return position - 1, if // rank greater than k if (rank > k) return position - 1; } // Increase position position++; } return n;}// Driver Codeint main(){ // Given array int arr[5] = { 2, 2, 3, 4, 5 }; int N = 5; // Given K int K = 4; // Function Call cout << rankLessThanK(arr, K, N); return 0;}// This code is contributed by hemanth gadarla |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG { // Function to find count of array // elements with rank less than or // equal to k static int rankLessThanK(int[] arr, int k, int n) { // Initialize rank and position int rank = 1; int position = 1; // Sort the given array Arrays.sort(arr); // Traverse array from right to left for (int i = n - 1; i >= 0; i--) { // Update rank with position, if // adjacent elements are unequal if (i == n - 1 || arr[i] != arr[i + 1]) { rank = position; // Return position - 1, if // rank greater than k if (rank > k) return position - 1; } // Increase position position++; } return n; } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 2, 2, 3, 4, 5 }; int N = arr.length; // Given K int K = 4; // Function Call System.out.println( rankLessThanK(arr, K, N)); }} |
Python3
# Python3 program for the # above approach# Function to find count of # array elements with rank # less than or equal to kdef rankLessThanK(arr, k, n): # Initialize rank and # position rank = 1; position = 1; # Sort the given array arr = sorted(arr) # Traverse array from # right to left for i in range(n - 1, -1, -1): # Update rank with position, # if adjacent elements are # unequal if (i == n - 1 or arr[i] != arr[i + 1]): rank = position; # Return position - 1, if # rank greater than k if (rank > k): return position - 1; # Increase position position += 1; return n;# Driver Codeif __name__ == '__main__': # Given array arr = [2, 2, 3, 4, 5]; N = len(arr); # Given K K = 4; # Function Call print(rankLessThanK(arr, K, N));# This code is contributed by gauravrajput1 |
C#
// C# program for the above approach using System; class GFG{ // Function to find count of array// elements with rank less than or// equal to kstatic int rankLessThanK(int[] arr, int k, int n){ // Initialize rank and position int rank = 1; int position = 1; // Sort the given array Array.Sort(arr); // Traverse array from right to left for(int i = n - 1; i >= 0; i--) { // Update rank with position, if // adjacent elements are unequal if (i == n - 1 || arr[i] != arr[i + 1]) { rank = position; // Return position - 1, if // rank greater than k if (rank > k) return position - 1; } // Increase position position++; } return n;} // Driver Codepublic static void Main(){ // Given array int[] arr = { 2, 2, 3, 4, 5 }; int N = arr.Length; // Given K int K = 4; // Function Call Console.WriteLine(rankLessThanK( arr, K, N));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program for the above approach// Function to find count of array// elements with rank less than or// equal to kfunction rankLessThanK(arr, k, n){ // Initialize rank and position let rank = 1; let position = 1; // Sort the given array arr.sort(); // Traverse array from right to left for(let i = n - 1; i >= 0; i--) { // Update rank with position, if // adjacent elements are unequal if (i == n - 1 || arr[i] != arr[i + 1]) { rank = position; // Return position - 1, if // rank greater than k if (rank > k) return position - 1; } // Increase position position++; } return n;}// Driver code// Given arraylet arr = [ 2, 2, 3, 4, 5 ];let N = arr.length;// Given Klet K = 4;// Function Calldocument.write(rankLessThanK(arr, K, N));// This code is contributed by splevel62 </script> |
5
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
