Given N non-overlapping ranges L[] and R[] where the every range starts after the previous range ends i.e. L[i] > R[i – 1] for all valid i. The task is to find the Kth element in the series which is formed after sorting all the elements in all the given ranges in ascending order.
Examples:
Input: L[] = {1, 8, 21}, R[] = {4, 10, 23}, K = 6
Output: 9
The generated series will be 1, 2, 3, 4, 8, 9, 10, 21, 22, 23
And the 6th element is 9
Input: L[] = {2, 11, 31}, R[] = {7, 15, 43}, K = 13
Output: 32
Approach: The idea is to use binary search. An array total to store the number of integers that are present upto ith index, now with the help of this array find out the index in which the kth integer will lie. Suppose that index is j, now compute the position of the kth smallest integer in the interval L[j] to R[j] and find the kth smallest integer using binary search where low will be L[j] and high will be R[j].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the kth element// of the required seriesint getKthElement(int n, int k, int L[], int R[]){ int l = 1; int h = n; // To store the number of integers that lie // upto the ith index int total[n + 1]; total[0] = 0; // Compute the number of integers for (int i = 0; i < n; i++) { total[i + 1] = total[i] + (R[i] - L[i]) + 1; } // Stores the index, lying from 1 // to n, int index = -1; // Using binary search, find the index // in which the kth element will lie while (l <= h) { int m = (l + h) / 2; if (total[m] > k) { index = m; h = m - 1; } else if (total[m] < k) l = m + 1; else { index = m; break; } } l = L[index - 1]; h = R[index - 1]; // Find the position of the kth element // in the interval in which it lies int x = k - total[index - 1]; while (l <= h) { int m = (l + h) / 2; if ((m - L[index - 1]) + 1 == x) { return m; } else if ((m - L[index - 1]) + 1 > x) h = m - 1; else l = m + 1; }}// Driver codeint main(){ int L[] = { 1, 8, 21 }; int R[] = { 4, 10, 23 }; int n = sizeof(L) / sizeof(int); int k = 6; cout << getKthElement(n, k, L, R); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the kth element// of the required seriesstatic int getKthElement(int n, int k, int L[], int R[]){ int l = 1; int h = n; // To store the number of integers that lie // upto the ith index int total[] = new int[n + 1]; total[0] = 0; // Compute the number of integers for (int i = 0; i < n; i++) { total[i + 1] = total[i] + (R[i] - L[i]) + 1; } // Stores the index, lying from 1 // to n, int index = -1; // Using binary search, find the index // in which the kth element will lie while (l <= h) { int m = (l + h) / 2; if (total[m] > k) { index = m; h = m - 1; } else if (total[m] < k) l = m + 1; else { index = m; break; } } l = L[index - 1]; h = R[index - 1]; // Find the position of the kth element // in the interval in which it lies int x = k - total[index - 1]; while (l <= h) { int m = (l + h) / 2; if ((m - L[index - 1]) + 1 == x) { return m; } else if ((m - L[index - 1]) + 1 > x) h = m - 1; else l = m + 1; } return k;}// Driver codepublic static void main(String[] args){ int L[] = { 1, 8, 21 }; int R[] = { 4, 10, 23 }; int n = L.length; int k = 6; System.out.println(getKthElement(n, k, L, R));}}// This code is contributed by Code_Mech |
Python3
# Python3 implementation of the approach # Function to return the kth element# of the required seriesdef getKthElement(n, k, L, R): l = 1 h = n # To store the number of integers that lie # upto the ith index total=[0 for i in range(n + 1)] total[0] = 0 # Compute the number of integers for i in range(n): total[i + 1] = total[i] + (R[i] - L[i]) + 1 # Stores the index, lying from 1 # to n, index = -1 # Using binary search, find the index # in which the kth element will lie while (l <= h): m = (l + h) // 2 if (total[m] > k): index = m h = m - 1 elif (total[m] < k): l = m + 1 else : index = m break l = L[index - 1] h = R[index - 1] # Find the position of the kth element # in the interval in which it lies x = k - total[index - 1] while (l <= h): m = (l + h) // 2 if ((m - L[index - 1]) + 1 == x): return m elif ((m - L[index - 1]) + 1 > x): h = m - 1 else: l = m + 1# Driver codeL=[ 1, 8, 21]R=[4, 10, 23]n = len(L)k = 6print(getKthElement(n, k, L, R))# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return the kth element// of the required seriesstatic int getKthElement(int n, int k, int[] L, int[] R){ int l = 1; int h = n; // To store the number of integers that lie // upto the ith index int[] total = new int[n + 1]; total[0] = 0; // Compute the number of integers for (int i = 0; i < n; i++) { total[i + 1] = total[i] + (R[i] - L[i]) + 1; } // Stores the index, lying from 1 // to n, int index = -1; // Using binary search, find the index // in which the kth element will lie while (l <= h) { int m = (l + h) / 2; if (total[m] > k) { index = m; h = m - 1; } else if (total[m] < k) l = m + 1; else { index = m; break; } } l = L[index - 1]; h = R[index - 1]; // Find the position of the kth element // in the interval in which it lies int x = k - total[index - 1]; while (l <= h) { int m = (l + h) / 2; if ((m - L[index - 1]) + 1 == x) { return m; } else if ((m - L[index - 1]) + 1 > x) h = m - 1; else l = m + 1; } return k;}// Driver codepublic static void Main(){ int[] L = { 1, 8, 21 }; int[] R = { 4, 10, 23 }; int n = L.Length; int k = 6; Console.WriteLine(getKthElement(n, k, L, R));}}// This code is contributed by Code_Mech |
PHP
<?php// PHP implementation of the approach // Function to return the kth element // of the required series function getKthElement($n, $k, $L, $R) { $l = 1; $h = $n; // To store the number of integers that lie // upto the ith index $total = array(); $total[0] = 0; // Compute the number of integers for ($i = 0; $i < $n; $i++) { $total[$i + 1] = $total[$i] + ($R[$i] - $L[$i]) + 1; } // Stores the index, lying from 1 // to n, $index = -1; // Using binary search, find the index // in which the kth element will lie while ($l <= $h) { $m = floor(($l + $h) / 2); if ($total[$m] > $k) { $index = $m; $h = $m - 1; } else if ($total[$m] < $k) $l = $m + 1; else { $index = $m; break; } } $l = $L[$index - 1]; $h = $R[$index - 1]; // Find the position of the kth element // in the interval in which it lies $x = $k - $total[$index - 1]; while ($l <= $h) { $m = floor(($l + $h) / 2); if (($m - $L[$index - 1]) + 1 == $x) { return $m; } else if (($m - $L[$index - 1]) + 1 > $x) $h = $m - 1; else $l = $m + 1; } } // Driver code $L = array( 1, 8, 21 ); $R = array( 4, 10, 23 ); $n = count($L);$k = 6; echo getKthElement($n, $k, $L, $R); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the kth element// of the required seriesfunction getKthElement(n,k,L,R){ let l = 1; let h = n; // To store the number of integers that lie // upto the ith index let total = new Array(n + 1); total[0] = 0; // Compute the number of integers for (let i = 0; i < n; i++) { total[i + 1] = total[i] + (R[i] - L[i]) + 1; } // Stores the index, lying from 1 // to n, let index = -1; // Using binary search, find the index // in which the kth element will lie while (l <= h) { let m = Math.floor((l + h) / 2); if (total[m] > k) { index = m; h = m - 1; } else if (total[m] < k) l = m + 1; else { index = m; break; } } l = L[index - 1]; h = R[index - 1]; // Find the position of the kth element // in the interval in which it lies let x = k - total[index - 1]; while (l <= h) { let m = Math.floor((l + h) / 2); if ((m - L[index - 1]) + 1 == x) { return m; } else if ((m - L[index - 1]) + 1 > x) h = m - 1; else l = m + 1; } return k;}// Driver codelet L = [1, 8, 21 ];let R = [ 4, 10, 23 ];let n = L.length;let k = 6;document.write(getKthElement(n, k, L, R));// This code is contributed by patel2127</script> |
Output:
9
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
