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
def getKthElement ( n , k , L , R ) : NEW_LINE INDENT l = 1 NEW_LINE h = n NEW_LINE total = [ 0 for i in range ( n + 1 ) ] NEW_LINE total [ 0 ] = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT total [ i + 1 ] = total [ i ] + ( R [ i ] - L [ i ] ) + 1 NEW_LINE DEDENT index = - 1 NEW_LINE while ( l <= h ) : NEW_LINE INDENT m = ( l + h ) // 2 NEW_LINE if ( total [ m ] > k ) : NEW_LINE INDENT index = m NEW_LINE h = m - 1 NEW_LINE DEDENT elif ( total [ m ] < k ) : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT else : NEW_LINE INDENT index = m NEW_LINE break NEW_LINE DEDENT DEDENT l = L [ index - 1 ] NEW_LINE h = R [ index - 1 ] NEW_LINE x = k - total [ index - 1 ] NEW_LINE while ( l <= h ) : NEW_LINE INDENT m = ( l + h ) // 2 NEW_LINE if ( ( m - L [ index - 1 ] ) + 1 == x ) : NEW_LINE INDENT return m NEW_LINE DEDENT elif ( ( m - L [ index - 1 ] ) + 1 > x ) : NEW_LINE INDENT h = m - 1 NEW_LINE DEDENT else : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT DEDENT DEDENT L = [ 1 , 8 , 21 ] NEW_LINE R = [ 4 , 10 , 23 ] NEW_LINE n = len ( L ) NEW_LINE k = 6 NEW_LINE print ( getKthElement ( n , k , L , R ) ) NEW_LINE