Kth largest even number in N intervals
Given a 2D array arr[] of N ranges, indicating integer intervals from L to R inclusive, and a number K, the task is to find Kth largest even number.
Examples:
Input: arr = {{12, 15}, {3, 9}, {2, 5}, {20, 25}, {16, 20}}, K = 9
Output: 6
Explanation: After merging, the ranges become {{2, 9}, {12, 25}} the, even numbers present in the ranges are {2, 4, 6, 8, 12, 14, 16, 18, 20, 22, 24} and the 9th largest even number is 6Input: arr = {{2, 4}, {8, 12}}, K = 4
Output: 4
Approach: The given problem can be solved by using the approach of merging overlapping Intervals. The idea is to sort the intervals with respect to the lower limit of the range and merge them to remove repetition of the integers. Then the below steps can be followed to solve the problem:
- If K<=0 or N=0 then return -1
- Initialize, L = arr[i].first and R = arr[i].second
- Initialize a variable range, to store even numbers within the range
- Iterate in a loop from idx to 0
- If R is odd
- range = floor((R – L + 1) / 2)
- If, K > range K = K – range
- Else return R – 2 * K + 1
- If R is even
- range = ceil((float)(R – L + 1) / 2)
- If, K > range K = K – range
- Else, R – 2 * K + 2
- If R is odd
- Return -1
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> #include <cmath> using namespace std; // Function to merge overlapping intervals // and return the Kth largest even number int calcEven(vector<pair< int , int > > V, int N, int k) { // Base Case if (k <= 0 || N == 0) return -1; // Sort the intervals in increasing order // according to their first element sort(V.begin(), V.end()); int i, idx = 0; // Merging the overlapping intervals for (i = 1; i < N; i++) { // If it overlaps with // the previous intervals if ((V[idx].second >= V[i].first) || (V[i].first == V[idx].second + 1)) { // Merge previous and current intervals V[idx].second = max(V[idx].second, V[i].second); } else { // Increment the index idx++; V[idx].second = V[i].second; V[idx].first = V[i].first; } } // Find Kth largest even number for (i = idx; i >= 0; i--) { // Initialize L and R int L = V[i].first; int R = V[i].second; // If R is odd if (R & 1) { // Calculate number of even // numbers within the range int range = (R - L + 1) / 2; // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k + 1); } else { // Calculate number of even // numbers within the range int range = ceil (( float )(R - L + 1) / 2); // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k + 2); } } // No Kth even number in the range // so return -1 return -1; } // Driver Code int main() { // Initialize the ranges vector<pair< int , int > > vec = { { 12, 15 }, { 3, 9 }, { 2, 5 }, { 20, 25 }, { 16, 20 } }; int N = vec.size(); // Initialize K int K = 9; // Print the answer cout << calcEven(vec, N, K); return 0; } |
Java
// Java implementation for the above approach import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; class GFG { static class Pair { int first = 0 ; int second = 0 ; public Pair( int first, int second) { this .first = first; this .second = second; } } // Function to merge overlapping intervals // and return the Kth largest even number public static int calcEven(ArrayList<Pair> V, int N, int k) { // Base Case if (k <= 0 || N == 0 ) return - 1 ; // Sort the intervals in increasing order // according to their first element Collections.sort(V, new Comparator<Pair>() { @Override public int compare(Pair p1, Pair p2) { return p1.first - p2.first; } }); int i, idx = 0 ; // Merging the overlapping intervals for (i = 1 ; i < N; i++) { // If it overlaps with // the previous intervals if ((V.get(idx).second >= V.get(i).first) || (V.get(i).first == V.get(idx).second + 1 )) { // Merge previous and current intervals V.get(idx).second = Math.max(V.get(idx).second, V.get(i).second); } else { // Increment the index idx++; V.get(idx).second = V.get(i).second; V.get(idx).first = V.get(i).first; } } // Find Kth largest even number for (i = idx; i >= 0 ; i--) { // Initialize L and R int L = V.get(i).first; int R = V.get(i).second; // If R is odd if ((R & 1 ) > 0 ) { // Calculate number of even // numbers within the range int range = (R - L + 1 ) / 2 ; // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k + 1 ); } else { // Calculate number of even // numbers within the range int range = ( int ) Math.ceil((R - L + 1 ) / 2 ); // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k + 2 ); } } // No Kth even number in the range // so return -1 return - 1 ; } // Driver Code public static void main(String args[]) { // Initialize the ranges ArrayList<Pair> vec = new ArrayList<Pair>(); vec.add( new Pair( 12 , 15 )); vec.add( new Pair( 3 , 9 )); vec.add( new Pair( 2 , 5 )); vec.add( new Pair( 20 , 25 )); vec.add( new Pair( 16 , 20 )); int N = vec.size(); // Initialize K int K = 9 ; // Print the answer System.out.println(calcEven(vec, N, K)); } } // This code is contributed by gfgking. |
Python3
# python implementation for the above approach import math # Function to merge overlapping intervals # and return the Kth largest even number def calcEven(V, N, k): # Base Case if (k < = 0 or N = = 0 ): return - 1 # Sort the intervals in increasing order # according to their first element V.sort() idx = 0 # Merging the overlapping intervals for i in range ( 1 , N): # If it overlaps with # the previous intervals if ((V[idx][ 1 ] > = V[i][ 0 ]) or (V[i][ 0 ] = = V[idx][ 1 ] + 1 )): # Merge previous and current intervals V[idx][ 1 ] = max (V[idx][ 1 ], V[i][ 1 ]) else : # Increment the index idx + = 1 V[idx][ 1 ] = V[i][ 1 ] V[idx][ 0 ] = V[i][ 0 ] # Find Kth largest even number for i in range (idx, - 1 , - 1 ): # Initialize L and R L = V[i][ 0 ] R = V[i][ 1 ] # If R is odd if (R & 1 ): # Calculate number of even # numbers within the range rng = (R - L + 1 ) / / 2 # if k > range then kth largest # even number is not in this range if (k > rng): k - = rng else : return (R - 2 * k + 1 ) else : # Calculate number of even # numbers within the range rng = math.ceil((R - L + 1 ) / 2 ) # if k > range then kth largest # even number is not in this range if (k > rng): k - = rng else : return (R - 2 * k + 2 ) # No Kth even number in the range # so return -1 return - 1 # Driver Code if __name__ = = "__main__" : # Initialize the ranges vec = [[ 12 , 15 ], [ 3 , 9 ], [ 2 , 5 ], [ 20 , 25 ], [ 16 , 20 ]] N = len (vec) # Initialize K K = 9 # Print the answer print (calcEven(vec, N, K)) # This code is contributed by rakeshsahni |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to merge overlapping intervals // and return the Kth largest even number function calcEven(V, N, k) { // Base Case if (k <= 0 || N == 0) return -1; // Sort the intervals in increasing order // according to their first element V.sort( function (a, b) { return a.first - b.first }) let i, idx = 0; // Merging the overlapping intervals for (i = 1; i < N; i++) { // If it overlaps with // the previous intervals if ((V[idx].second >= V[i].first) || (V[i].first == V[idx].second + 1)) { // Merge previous and current intervals V[idx].second = Math.max(V[idx].second, V[i].second); } else { // Increment the index idx++; V[idx].second = V[i].second; V[idx].first = V[i].first; } } // Find Kth largest even number for (i = idx; i >= 0; i--) { // Initialize L and R let L = V[i].first; let R = V[i].second; // If R is odd if (R & 1) { // Calculate number of even // numbers within the range let range = (R - L + 1) / 2; // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k + 1); } else { // Calculate number of even // numbers within the range let range = Math.ceil((R - L + 1) / 2); // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k + 2); } } // No Kth even number in the range // so return -1 return -1; } // Driver Code // Initialize the ranges let vec = [{ first: 12, second: 15 }, { first: 3, second: 9 }, { first: 2, second: 5 }, { first: 20, second: 25 }, { first: 16, second: 20 }]; let N = vec.length; // Initialize K let K = 9; // Print the answer document.write(calcEven(vec, N, K)); // This code is contributed by Potta Lokesh </script> |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; using System.Linq; public class GFG { static void Main( string [] args) { // Initialize the ranges List<Tuple< int , int >> vec = new List<Tuple< int , int >> { Tuple.Create(12, 15), Tuple.Create(3, 9), Tuple.Create(2, 5), Tuple.Create(20, 25), Tuple.Create(16, 20) }; int N = vec.Count; // Initialize K int K = 9; // Print the answer Console.WriteLine(CalcEven(vec, N, K)); } // Function to merge overlapping intervals // and return the Kth largest even number static int CalcEven(List<Tuple< int , int >> V, int N, int k) { // Base Case if (k <= 0 || N == 0) return -1; // Sort the intervals in increasing order // according to their first element V = V.OrderBy(x => x.Item1).ToList(); int i, idx = 0; // Merging the overlapping intervals for (i = 1; i < N; i++) { // If it overlaps with // the previous intervals if ((V[idx].Item2 >= V[i].Item1) || (V[i].Item1 == V[idx].Item2 + 1)) { // Merge previous and current intervals V[idx] = Tuple.Create(V[idx].Item1, Math.Max(V[idx].Item2, V[i].Item2)); } else { // Increment the index idx++; V[idx] = Tuple.Create(V[i].Item1, V[i].Item2); } } // Find Kth largest even number for (i = idx; i >= 0; i--) { // Initialize L and R int L = V[i].Item1; int R = V[i].Item2; // If R is odd if (R % 2 != 0) { // Calculate number of even // numbers within the range int range = (R - L + 1) / 2; // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k + 1); } else { // Calculate number of even // numbers within the range int range = ( int )Math.Ceiling(( double )(R - L + 1) / 2); // if k > range then kth largest // even number is not in this range if (k > range) { k -= range; } else return (R - 2 * k +2); } } return -1 ; } } |
6
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Contact Us