Count distinct elements from a range of a sorted sequence from a given frequency array | Function to find the first index with value is at least element ; Update the value of left ; Binary search for the element ; Find the middle element ; Check if the value lies between the elements at index mid - 1 and mid ; Check in the right subarray ; Update the value of left ; Check in left subarray ; Update the value of right ; Function to count the number of distinct elements over the range [ L , R ] in the sorted sequence ; Stores the count of distinct elements ; Create the prefix sum array ; Update the value of count ; Update the value of pref [ i ] ; Calculating the first index of L and R using binary search ; Print the resultant count ; Driver Code
function binarysearch ( array , right , element ) { let left = 1 ; while ( left <= right ) { let mid = Math . floor ( ( left + right / 2 ) ) ; if ( array [ mid ] == element ) { return mid ; } if ( mid - 1 > 0 && array [ mid ] > element && array [ mid - 1 ] < element ) { return mid ; } else if ( array [ mid ] < element ) { left = mid + 1 ; } else { right = mid - 1 ; } } return 1 ; } function countDistinct ( arr , L , R ) { let count = 0 ; let pref = Array . from ( { length : arr . length + 1 } , ( _ , i ) => 0 ) ; for ( let i = 1 ; i <= arr . length ; ++ i ) { count += arr [ i - 1 ] ; pref [ i ] = count ; } let left = binarysearch ( pref , arr . length + 1 , L ) ; let right = binarysearch ( pref , arr . length + 1 , R ) ; document . write ( ( right - left ) + 1 ) ; } let arr = [ 3 , 6 , 7 , 1 , 8 ] ; let L = 3 ; let R = 7 ; countDistinct ( arr , L , R ) ;