Given an array arr[ ] of size N, the task is to find the rank of the remaining element in an array after performing the given operation:
- In each operation choose elements from both ends and delete them and insert the max of those values at the position of the left element and move one step towards the center from both ends and keep performing this operation.
- In the next cycle keep performing the same operation but instead of max, insert min of the elements this time.
- Perform this operation in alternate cycles until there is only one element left in the array.
- The rank is the position of the remaining element in the original array when it is sorted in increasing order. (The elements with same values are considered only for the sorted order)
Examples:
Input: arr = {4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89}
Output: 6
Explanation: See the diagram given below
24 is the 6th smallest element. The elements with same values are considered once.
Input: N = {20, 4, 5, 35, 6, 22, 4, 34}
Output: 6
Approach: The solution is based on two pointer approach. Follow the steps mentioned below:
- Take c as 1 which will indicate the number of iterations.
- Take 2 pointers, start as zero and end as N-1.
- Compare element at index s and e.
- If c is odd then take the maximum of the element else take the minimum of element and store in an array.
- Increment s, decrement e and repeat till s != e.
- Increment c by 1
- Repeat step 2 till the length of arr becomes 1.
- Remove duplicate from arr[] and sort it, now find the rank of the remaining element.
Below is the implementation of the above approach.
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find rank of number in arrayint rankOfNum(vector<int>& num){ // Copying array to S vector<int> S = num; // c count no of iterations int c = 1; while (S.size() != 1) { // s is starting index int s = 0; // e is ending index int e = S.size() - 1; // Empty array to store // result of comparisons. vector<int> l; // loop till s <= e while (s <= e) { // In odd iterations take // maximum of element. if (c % 2 == 1) l.push_back(max(S[s], S[e])); // In even Iterations // take minimum of element. else { l.push_back(min(S[s], S[e])); } // Increment s by 1 // and decrement e by 1 s += 1; e -= 1; } // Assigning l to S S = l; // Increment iteration value by 1 c += 1; } // Converting list into set and again to list // so that all duplicate will get removed set<int> setx; for (auto dt : num) setx.insert(dt); // Finding index of remained element int p = distance(setx.begin(), setx.find(S[0])); // Returning the rank of element return p + 1;}// Driver codeint main(){ // Original array vector<int> arr = { 4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89 }; // Calling function int s = rankOfNum(arr); // Print its rank cout << s; return 0;}// This code is contributed by rakeshsahni |
Java
// Java code for the above approachimport java.util.*;class GFG{// Function to find rank of number in arraystatic int rankOfNum(Integer[] num){ // Copying array to S List<Integer> S = Arrays.asList(num); // c count no of iterations int c = 1; while (S.size() != 1) { // s is starting index int s = 0; // e is ending index int e = S.size() - 1; // Empty array to store // result of comparisons. ArrayList<Integer> l = new ArrayList<Integer>(); // loop till s <= e while (s <= e) { // In odd iterations take // maximum of element. if (c % 2 == 1) l.add(Math.max(S.get(s), S.get(e))); // In even Iterations // take minimum of element. else { l.add(Math.min(S.get(s), S.get(e))); } // Increment s by 1 // and decrement e by 1 s += 1; e -= 1; } // Assigning l to S S = l; // Increment iteration value by 1 c += 1; } // Converting list into set and again to list // so that all duplicate will get removed HashSet<Integer> setx = new HashSet<Integer>(); for (int dt : num) setx.add(dt); // Finding index of remained element List<Integer> l = new LinkedList<>(setx); Collections.sort(l); int p = l.indexOf(S.get(0)); // Returning the rank of element return p + 1;}// Driver codepublic static void main(String[] args){ // Original array Integer[] arr = { 4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89 }; // Calling function int s = rankOfNum(arr); // Print its rank System.out.print(s);}}// This code is contributed by 29AjayKumar |
Python3
# Python code to implement above approach# Function to find rank of number in arraydef rankOfNum(num): # Copying array to S S = num[:] # c count no of iterations c = 1 while len(S) != 1: # s is starting index s = 0 # e is ending index e = len(S) - 1 # Empty array to store # result of comparisons. l = [] # loop till s <= e while s <= e: # In odd iterations take # maximum of element. if c % 2 == 1: l.append(max(S[s], S[e])) # In even Iterations # take minimum of element. else: l.append(min(S[s], S[e])) # Increment s by 1 # and decrement e by 1 s += 1 e -= 1 # Assigning l to S S = l # Increment iteration value by 1 c += 1 # Converting list into set and again to list # so that all duplicate will get removed setx = list(set(num)) # Sorting to get rank setx.sort() # Finding index of remained element p = setx.index(S[0]) # Returning the rank of element return p + 1if __name__ == "__main__": # Original array arr = [4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89] # Calling function s = rankOfNum(arr) # Print its rank print(str(s)) |
C#
// C# code for the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG { // Function to find rank of number in array static int rankOfNum(List<int> num) { // Copying array to S List<int> S = num; // c count no of iterations int c = 1; while (S.Count != 1) { // s is starting index int s = 0; // e is ending index int e = S.Count - 1; // Empty array to store // result of comparisons. List<int> l = new List<int>(); // loop till s <= e while (s <= e) { // In odd iterations take // maximum of element. if (c % 2 == 1) l.Add(Math.Max(S[s], S[e])); // In even Iterations // take minimum of element. else { l.Add(Math.Min(S[s], S[e])); } // Increment s by 1 // and decrement e by 1 s += 1; e -= 1; } // Assigning l to S S = l; // Increment iteration value by 1 c += 1; } // Converting list into set and again to list // so that all duplicate will get removed HashSet<int> setx = new HashSet<int>(); foreach(var dt in num) setx.Add(dt); // Finding index of remained element List<int> setxList = setx.ToList(); setxList.Sort(); int p = setxList.IndexOf(S[0]); // Returning the rank of element return p + 1; } // Driver code public static void Main() { // Original array List<int> arr = new List<int>() { 4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89 }; // Calling function int s = rankOfNum(arr); // Print its rank Console.Write(s); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to find rank of number in array function rankOfNum(num) { // Copying array to S let S = [...num] // c count no of iterations c = 1 while (S.length != 1) { // s is starting index s = 0 // e is ending index e = S.length - 1 // Empty array to store // result of comparisons. l = [] // loop till s <= e while (s <= e) { // In odd iterations take // maximum of element. if (c % 2 == 1) l.push(Math.max(S[s], S[e])) // In even Iterations // take minimum of element. else { l.push(Math.min(S[s], S[e])) } // Increment s by 1 // and decrement e by 1 s += 1 e -= 1 } // Assigning l to S S = [...l] // Increment iteration value by 1 c += 1 } // Converting list into set and again to list // so that all duplicate will get removed let setx = new Set([...num]) // Sorting to get rank t = [...setx].sort(function (a, b) { return a - b }) // Finding index of remained element let p = t.indexOf(S[0]) // Returning the rank of element return p + 1 } // Original array arr = [4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89] // Calling function s = rankOfNum(arr) // Print its rank document.write((s)) // This code is contributed by Potta Lokesh </script> |
Output
6
Time Complexity: O(N)
Space Complexity: O(N), since n extra space has been taken
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
