Find the kth element in the series generated by the given N ranges | 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
< ? php function getKthElement ( $ n , $ k , $ L , $ R ) { $ l = 1 ; $ h = $ n ; $ total = array ( ) ; $ total [ 0 ] = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ total [ $ i + 1 ] = $ total [ $ i ] + ( $ R [ $ i ] - $ L [ $ i ] ) + 1 ; } $ index = -1 ; 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 ] ; $ 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 ; } } $ L = array ( 1 , 8 , 21 ) ; $ R = array ( 4 , 10 , 23 ) ; $ n = count ( $ L ) ; $ k = 6 ; echo getKthElement ( $ n , $ k , $ L , $ R ) ; ? >