Find the kth element in the series generated by the given N ranges | C ++ implementation of the approach ; Function to return the kth element of the required series ; To store the number of integers that lie upto the ith index ; Compute the number of integers ; Stores the index , lying from 1 to n , ; Using binary search , find the index in which the kth element will lie ; Find the position of the kth element in the interval in which it lies ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getKthElement ( int n , int k , int L [ ] , int R [ ] ) { int l = 1 ; int h = n ; int total [ n + 1 ] ; total [ 0 ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) { total [ i + 1 ] = total [ i ] + ( R [ i ] - L [ i ] ) + 1 ; } int index = -1 ; 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 ] ; 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 ; } } int 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 ; }