Count of array elements that can be found using Randomized Binary Search on every array element | C ++ program for the above approach ; Function to find minimum count of array elements found by repeatedly applying Randomized Binary Search ; Stores count of array elements ; smallestRight [ i ] : Stores the smallest array element on the right side of i ; Update smallestRight [ 0 ] ; Traverse the array from right to left ; Update smallestRight [ i ] ; Stores the largest element upto i - th index ; Stores the minimum count of elements found by repeatedly applying Randomized Binary Search ; If largest element on left side is less than smallest element on right side ; Update ans ; Update mn ; Driver Code ; Given array ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getDefiniteFinds ( vector < int > & arr ) { int n = arr . size ( ) ; vector < int > smallestRight ( n + 1 ) ; smallestRight [ n ] = INT_MAX ; for ( int i = n - 1 ; i >= 0 ; i -- ) { smallestRight [ i ] = min ( smallestRight [ i + 1 ] , arr [ i ] ) ; } int mn = INT_MIN ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( mn < arr [ i ] and arr [ i ] < smallestRight [ i + 1 ] ) { ans ++ ; } mn = max ( arr [ i ] , mn ) ; } return ans ; } int main ( ) { vector < int > arr = { 5 , 4 , 9 } ; cout << getDefiniteFinds ( arr ) << endl ; }