Given an array arr[] of strings representing large numbers and an integer K, the task is to find Kth largest integer in given array.
Examples:
Input: arr[] = { “10”, “7”, “3”, “6” }, K = 3
Output: “6”
Explanation : Arranging the array in non-decreasing manner will give { “3”, “6”, “7”, “10” }.
Clearly 3rd largest integer is 6.Input: arr[] = { “10”, “7”, “6”, “7”, “11” }, K = 2
Output: “10”
Explanation: Arranging the array in non-decreasing manner will give { “6”, “7”, “7”, “10”, “11” }
Clearly 2nd largest integer is 10.
Naive Approach (Incorrect): Usually such kind of problems can be solved by converting strings to integers and then finding the Kth largest number. But since we are talking about large numbers, i.e., strings representing integers up to length 100, so it not possible to convert them to integers.
Correct Approach: This problem can be solved using the Greedy Approach by implementing a custom comparator.
Follow the steps below to solve the given problem.
- Use custom sorting to sort the array in non-decreasing order.
- In the custom sort function there will be two cases :
- The size of two passed strings is equal, then swap only when string one is lexicographically smaller than the other.
- The size of two passed strings is un-equal, then swap only when the size of one string is smaller than the other.
- After sorting print Kth largest integer.
Below is the implementation of the above approach:
C++
// C++ implementation for above approach#include <bits/stdc++.h>using namespace std;// Custom comparator to sort// the array of stringsbool comp(string& a, string& b){ // If sizes of string a and b are equal // then return true if a is // lexicographically smaller than b if (a.size() == b.size()) return a < b; // Return true if size of a // is smaller than b return a.size() < b.size();}// Function that returns// kth largest integerstring kthLargestInteger( string arr[], int n, int k){ // Sort string arr in non-decreasing order // using custom comparator function sort(arr, arr + n, comp); return arr[n - k];}// Driver Codeint main(){ int N = 4; string arr[N] = { "10", "7", "3", "6" }; int K = 4; cout << kthLargestInteger(arr, N, K) << endl; return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG { // Custom comparator to sort // the array of strings // Function that returns // kth largest integer static String kthLargestInteger(String arr[], int n, int k) { // Sort string arr in non-decreasing order // using custom comparator function Arrays.sort(arr, new Comparator<String>() { @Override public int compare(String a, String b) { return Integer.valueOf(a).compareTo( Integer.valueOf(b)); } }); return arr[n - k]; } // Driver Code public static void main(String[] args) { int N = 4; String arr[] = { "10", "7", "3", "6" }; int K = 4; System.out.println(kthLargestInteger(arr, N, K)); }}// This code is contributed by Potta Lokesh |
Python3
# Python 3 implementation for above approach# Function that returns# kth largest integerdef kthLargestInteger( arr, n, k): # Sort string arr in non-decreasing order # using custom comparator function arr = [int(i) for i in arr] arr.sort() return arr[n - k]# Driver Codeif __name__ == "__main__": N = 4 arr = ["10", "7", "3", "6"] K = 4 print(kthLargestInteger(arr, N, K)) # This code is contributed by ukasp. |
C#
// C# code for the above approachusing System;public class GFG { // Custom comparator to sort // the array of strings // Function that returns // kth largest integer static String kthLargestint(String []arr, int n, int k) { // Sort string arr in non-decreasing order // using custom comparator function Array.Sort(arr,CompareStrings); return arr[n - k]; } static int CompareStrings(string a, string b) { return Int32.Parse(a).CompareTo( Int32.Parse(b)); } // Driver Code public static void Main(String[] args) { int N = 4; String []arr = { "10", "7", "3", "6" }; int K = 4; Console.WriteLine(kthLargestint(arr, N, K)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation for above approach// Custom comparator to sort// the array of stringsfunction comp(a, b) { // If sizes of string a and b are equal // then return true if a is // lexicographically smaller than b if (a.length == b.length) return a - b; // Return true if size of a // is smaller than b return (a.length - b.length);}// Function that returns// kth largest integerfunction kthLargestInteger(arr, n, k) { // Sort string arr in non-decreasing order // using custom comparator function arr.sort(comp); console.log(arr) return arr[n - k];}// Driver Codelet N = 4;let arr = ["10", "7", "3", "6"];let K = 4;document.write(kthLargestInteger(arr, N, K))// This code is contributed by saurbh_jaiswal.</script> |
3
Time Complexity: O(N * log N), Where N is the size of the array.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
