Given an array arr[] of size N, the task is to find the minimum count of array elements found by applying the Randomized Binary Search for each array elements.
Examples:
Input: arr[] = { 5, 4, 9 }
Output: 2
Explanation:
Applying Randomized Binary Search for arr[0] in the array.
Initially, search space is [0, 2]
Suppose pivot = 1 and arr[pivot] < arr[0]. Therefore, the new search space is [2, 2] and arr[0] not found in the search space.
For arr[1], search space is [0, 2].
Suppose pivot = 0 and arr[pivot] > arr[0]. Therefore, the new search space is [0, 0] and arr[1] not found in the search space.
For arr[2], search space is [0, 2].
Selecting any element as pivot, arr[2] can be found.Input: arr[] = { 1, 2, 3, 4 }
Output: 4
Approach: The idea is to count the array elements before which all array elements are smaller than it, and after which all are greater than it. Follow the steps below to solve the problem:
- Initialize an array, say smallestRight[] to store the smallest element on the right side of each array element.
- Traverse the array in reverse and update smallestRight[i] = min(smallestRight[ i + 1], arr[i]).
- Traverse the array and store the largest element on the left side of each array element and check if the largest element on the left side is less than the smallest element on the right side or not. If found to be true, then increment the count.
- Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum count of// array elements found by repeatedly// applying Randomized Binary Searchint getDefiniteFinds(vector<int>& arr){ // Stores count of array elements int n = arr.size(); // smallestRight[i]: Stores the smallest // array element on the right side of i vector<int> smallestRight(n + 1); // Update smallestRight[0] smallestRight[n] = INT_MAX; // Traverse the array from right to left for (int i = n - 1; i >= 0; i--) { // Update smallestRight[i] smallestRight[i] = min(smallestRight[i + 1], arr[i]); } // Stores the largest element // upto i-th index int mn = INT_MIN; // Stores the minimum count of // elements found by repeatedly // applying Randomized Binary Search int ans = 0; for (int i = 0; i < n; i++) { // If largest element on left side is // less than smallest element on right side if (mn < arr[i] and arr[i] < smallestRight[i + 1]) { // Update ans ans++; } // Update mn mn = max(arr[i], mn); } return ans;}// Driver Codeint main(){ // Given array vector<int> arr = { 5, 4, 9 }; // Function Call cout << getDefiniteFinds(arr) << endl;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ // Function to find minimum count of // array elements found by repeatedly // applying Randomized Binary Search static int getDefiniteFinds(int[] arr) { // Stores count of array elements int n = arr.length; // smallestRight[i]: Stores the smallest // array element on the right side of i int[] smallestRight = new int[n + 1]; // Update smallestRight[0] smallestRight[n] = Integer.MAX_VALUE; // Traverse the array from right to left for (int i = n - 1; i >= 0; i--) { // Update smallestRight[i] smallestRight[i] = Math.min(smallestRight[i + 1], arr[i]); } // Stores the largest element // upto i-th index int mn = Integer.MIN_VALUE; // Stores the minimum count of // elements found by repeatedly // applying Randomized Binary Search int ans = 0; for (int i = 0; i < n; i++) { // If largest element on left side is // less than smallest element on right side if (mn < arr[i] && arr[i] < smallestRight[i + 1]) { // Update ans ans++; } // Update mn mn = Math.max(arr[i], mn); } return ans; } // Driver Code public static void main(String[] args) { // Given array int[] arr = new int[] { 5, 4, 9 }; // Function Call System.out.println(getDefiniteFinds(arr)); }}// This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approachimport sys# Function to find minimum count of# array elements found by repeatedly# applying Randomized Binary Searchdef getDefiniteFinds(arr): # Stores count of array elements n = len(arr) # smallestRight[i]: Stores the smallest # array element on the right side of i smallestRight = [0] * (n + 1) # Update smallestRight[0] smallestRight[n] = sys.maxsize # Traverse the array from right to left for i in range(n - 1, -1, -1): # Update smallestRight[i] smallestRight[i] = min( smallestRight[i + 1], arr[i]) # Stores the largest element # upto i-th index mn = -sys.maxsize - 1 # Stores the minimum count of # elements found by repeatedly # applying Randomized Binary Search ans = 0 for i in range(n): # If largest element on left side is # less than smallest element on right side if (mn < arr[i] and arr[i] < smallestRight[i + 1]): # Update ans ans += 1 # Update mn mn = max(arr[i], mn) return ans# Driver Code# Given arrayarr = [ 5, 4, 9 ]# Function Callprint(getDefiniteFinds(arr))# This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approachusing System;class GFG { // Function to find minimum count of // array elements found by repeatedly // applying Randomized Binary Search static int getDefiniteFinds(int[] arr) { // Stores count of array elements int n = arr.Length; // smallestRight[i]: Stores the smallest // array element on the right side of i int[] smallestRight = new int[n + 1]; // Update smallestRight[0] smallestRight[n] = Int32.MaxValue; // Traverse the array from right to left for (int i = n - 1; i >= 0; i--) { // Update smallestRight[i] smallestRight[i] = Math.Min(smallestRight[i + 1], arr[i]); } // Stores the largest element // upto i-th index int mn = Int32.MinValue; // Stores the minimum count of // elements found by repeatedly // applying Randomized Binary Search int ans = 0; for (int i = 0; i < n; i++) { // If largest element on left side is // less than smallest element on right side if (mn < arr[i] && arr[i] < smallestRight[i + 1]) { // Update ans ans++; } // Update mn mn = Math.Max(arr[i], mn); } return ans; } // Driver Code static public void Main() { // Given array int[] arr = new int[] { 5, 4, 9 }; // Function Call Console.WriteLine(getDefiniteFinds(arr)); }}// This code is contributed by Dharanendra L V |
Javascript
<script>// javascript program of the above approach // Function to find minimum count of // array elements found by repeatedly // applying Randomized Binary Search function getDefiniteFinds(arr) { // Stores count of array elements let n = arr.length; // smallestRight[i]: Stores the smallest // array element on the right side of i let smallestRight = new Array(n+1).fill(0); // Update smallestRight[0] smallestRight[n] = Number.MAX_VALUE; // Traverse the array from right to left for (let i = n - 1; i >= 0; i--) { // Update smallestRight[i] smallestRight[i] = Math.min(smallestRight[i + 1], arr[i]); } // Stores the largest element // upto i-th index let mn = Number.MIN_VALUE; // Stores the minimum count of // elements found by repeatedly // applying Randomized Binary Search let ans = 0; for (let i = 0; i < n; i++) { // If largest element on left side is // less than smallest element on right side if (mn < arr[i] && arr[i] < smallestRight[i + 1]) { // Update ans ans++; } // Update mn mn = Math.max(arr[i], mn); } return ans; } // Driver Code // Given array let arr = [ 5, 4, 9 ]; // Function Call document.write(getDefiniteFinds(arr)); // This code is contributed by chinmoy1997pal.</script> |
Output:
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
