Count distinct elements from a range of a sorted sequence from a given frequency array | C ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binarysearch ( int array [ ] , int right , int element ) { int left = 1 ; while ( left <= right ) { int mid = ( 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 ; } void countDistinct ( vector < int > arr , int L , int R ) { int count = 0 ; int pref [ arr . size ( ) + 1 ] ; for ( int i = 1 ; i <= arr . size ( ) ; ++ i ) { count += arr [ i - 1 ] ; pref [ i ] = count ; } int left = binarysearch ( pref , arr . size ( ) + 1 , L ) ; int right = binarysearch ( pref , arr . size ( ) + 1 , R ) ; cout << right - left + 1 ; } int main ( ) { vector < int > arr { 3 , 6 , 7 , 1 , 8 } ; int L = 3 ; int R = 7 ; countDistinct ( arr , L , R ) ; }