Given a sorted array of n distinct integers rotated at some point. Given a value x. The problem is to count all the elements in the array which are less than or equal to x.
Examples:
Input : arr[] = {4, 5, 8, 1, 3},
x = 6
Output : 4
Input : arr[] = {6, 10, 12, 15, 2, 4, 5},
x = 14
Output : 6
Naive Approach: One by one traverse all the elements of the array and count the one’s which are less than or equal to x. Time Complexity O(n).
Efficient Approach: Prerequisite of a modified binary search which can return the index of the largest element smaller than or equal to a given value in a sorted range of arr[l…h].
Refer this post for the required modified binary search:
Steps:
- Find the index of the smallest element in rotated sorted array. Refer this post. Let it be min_index.
- If x <= arr[n-1], find the index of the largest element smaller than or equal to x in the sorted range arr[min_index…n-1] with the help of modified binary search.
Let it be index1. Now, count = index1 + 1 – min_index.- If 0 <= (min_index -1) && x <= arr[min_index – 1], find the index of the largest element smaller than or equal to x in the sorted range arr[0…min_index-1] with the help of modified binary search. Let it be index2. Now, count = n – min_index + index2 + 1.
- Else count = n.
C++
// C++ implementation to count elements less than or // equal to a given value in a sorted rotated array#include <bits/stdc++.h>using namespace std;// function to find the minimum element's indexint findMinIndex(int arr[], int low, int high){ // This condition is needed to handle the case when // array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid int mid = (low + high) / 2; // Check if element (mid+1) is minimum element. Consider // the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid+1] < arr[mid]) return (mid + 1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to left half or right half if (arr[high] > arr[mid]) return findMinIndex(arr, low, mid-1); return findMinIndex(arr, mid+1, high);}// function returns the index of largest element // smaller than equal to 'x' in 'arr[l...h]'. // If no such element exits in the given range, // then it returns l-1. int binary_search(int arr[], int l, int h, int x){ while (l <= h) { int mid = (l+h) / 2; // if 'x' is less than or equal to arr[mid], // then search in arr[mid+1...h] if (arr[mid] <= x) l = mid + 1; // else search in arr[l...mid-1] else h = mid - 1; } // required index return h;}// function to count elements less than // or equal to a given valueint countEleLessThanOrEqual(int arr[], int n, int x){ // index of the smallest element in the array int min_index = findMinIndex(arr, 0, n-1); // if largest element smaller than or equal to 'x' lies // in the sorted range arr[min_index...n-1] if (x <= arr[n-1]) return (binary_search(arr, min_index, n-1, x) + 1 - min_index); // if largest element smaller than or equal to 'x' lies // in the sorted range arr[0...min_index-1] if ((min_index - 1) >= 0 && x <= arr[min_index - 1]) return (n - min_index + binary_search(arr, 0, min_index-1, x) + 1); // else all the elements of the array // are less than 'x' return n; }// Driver program to test aboveint main(){ int arr[] = {6, 10, 12, 15, 2, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int x = 14; cout << "Count = " << countEleLessThanOrEqual(arr, n, x); return 0;} |
Java
// Java implementation to count elements// less than or equal to a given// value in a sorted rotated arrayclass GFG { // function to find the minimum // element's indexstatic int findMinIndex(int arr[], int low, int high) { // This condition is needed to handle // the case when array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid int mid = (low + high) / 2; // Check if element (mid+1) is // minimum element. Consider // the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid + 1] < arr[mid]) return (mid + 1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to // left half or right half if (arr[high] > arr[mid]) return findMinIndex(arr, low, mid - 1); return findMinIndex(arr, mid + 1, high);}// function returns the index of largest element// smaller than equal to 'x' in 'arr[l...h]'.// If no such element exits in the given range,// then it returns l-1.static int binary_search(int arr[], int l, int h, int x) { while (l <= h) { int mid = (l + h) / 2; // if 'x' is less than or equal to arr[mid], // then search in arr[mid+1...h] if (arr[mid] <= x) l = mid + 1; // else search in arr[l...mid-1] else h = mid - 1; } // required index return h;}// function to count elements less than// or equal to a given valuestatic int countEleLessThanOrEqual(int arr[], int n, int x) { // index of the smallest element in the array int min_index = findMinIndex(arr, 0, n - 1); // if largest element smaller than or // equal to 'x' lies in the sorted // range arr[min_index...n-1] if (x <= arr[n - 1]) return (binary_search(arr, min_index, n - 1, x) + 1 - min_index); // if largest element smaller than or // equal to 'x' lies in the sorted // range arr[0...min_index-1] if ((min_index - 1) >= 0 && x <= arr[min_index - 1]) return (n - min_index + binary_search(arr, 0, min_index - 1, x) + 1); // else all the elements of the array // are less than 'x' return n;}// Driver codepublic static void main(String[] args) { int arr[] = {6, 10, 12, 15, 2, 4, 5}; int n = arr.length; int x = 14; System.out.print("Count = " + countEleLessThanOrEqual(arr, n, x));}}// This code is contributed by Anant Agarwal. |
Python3
# Python implementation to# count elements less than or # equal to a given value# in a sorted rotated array# function to find the# minimum element's indexdef findMinIndex(arr,low,high): # This condition is needed # to handle the case when # array is not rotated at all if (high < low): return 0 # If there is only one element left if (high == low): return low # Find mid mid = (low + high) // 2 # Check if element (mid+1) is # minimum element. Consider # the cases like {3, 4, 5, 1, 2} if (mid < high and arr[mid+1] < arr[mid]): return (mid + 1) # Check if mid itself # is minimum element if (mid > low and arr[mid] < arr[mid - 1]): return mid # Decide whether we need to # go to left half or right half if (arr[high] > arr[mid]): return findMinIndex(arr, low, mid-1) return findMinIndex(arr, mid+1, high)# function returns the # index of largest element # smaller than equal to # 'x' in 'arr[l...h]'. # If no such element exits# in the given range, # then it returns l-1. def binary_search(arr,l,h,x): while (l <= h): mid = (l+h) // 2 # if 'x' is less than # or equal to arr[mid], # then search in arr[mid+1...h] if (arr[mid] <= x): l = mid + 1 # else search in arr[l...mid-1] else: h = mid - 1 # required index return h # function to count# elements less than # or equal to a given valuedef countEleLessThanOrEqual(arr,n,x): # index of the smallest # element in the array min_index = findMinIndex(arr, 0, n-1) # if largest element smaller # than or equal to 'x' lies # in the sorted range arr[min_index...n-1] if (x <= arr[n-1]): return (binary_search(arr, min_index, n-1, x) + 1 - min_index) # if largest element smaller # than or equal to 'x' lies # in the sorted range arr[0...min_index-1] if ((min_index - 1) >= 0 and x <= arr[min_index - 1]): return (n - min_index + binary_search(arr, 0, min_index-1, x) + 1) # else all the elements of the array # are less than 'x' return n # driver codearr = [6, 10, 12, 15, 2, 4, 5]n = len(arr)x = 14print("Count = ",end="")print(countEleLessThanOrEqual(arr, n, x))# This code is contributed# by Anant Agarwal. |
C#
// C# implementation to count elements// less than or equal to a given// value in a sorted rotated arrayusing System; public class GFG { // function to find the minimum // element's index static int findMinIndex(int []arr, int low, int high) { // This condition is needed to handle // the case when array is not rotated // at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid int mid = (low + high) / 2; // Check if element (mid+1) is // minimum element. Consider // the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid + 1] < arr[mid]) return (mid + 1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to // left half or right half if (arr[high] > arr[mid]) return findMinIndex(arr, low, mid - 1); return findMinIndex(arr, mid + 1, high); } // function returns the index of largest element // smaller than equal to 'x' in 'arr[l...h]'. // If no such element exits in the given range, // then it returns l-1. static int binary_search(int []arr, int l, int h, int x) { while (l <= h) { int mid = (l + h) / 2; // if 'x' is less than or equal to // arr[mid], then search in // arr[mid+1...h] if (arr[mid] <= x) l = mid + 1; // else search in arr[l...mid-1] else h = mid - 1; } // required index return h; } // function to count elements less than // or equal to a given value static int countEleLessThanOrEqual(int []arr, int n, int x) { // index of the smallest element in // the array int min_index = findMinIndex(arr, 0, n - 1); // if largest element smaller than or // equal to 'x' lies in the sorted // range arr[min_index...n-1] if (x <= arr[n - 1]) return (binary_search(arr, min_index, n - 1, x) + 1 - min_index); // if largest element smaller than or // equal to 'x' lies in the sorted // range arr[0...min_index-1] if ((min_index - 1) >= 0 && x <= arr[min_index - 1]) return (n - min_index + binary_search(arr, 0, min_index - 1, x) + 1); // else all the elements of the array // are less than 'x' return n; } // Driver code public static void Main() { int []arr = {6, 10, 12, 15, 2, 4, 5}; int n = arr.Length; int x = 14; Console.Write("Count = " + countEleLessThanOrEqual(arr, n, x)); }}// This code is contributed by Sam007. |
PHP
<?php // PHP implementation to count elements // less than or equal to a given value // in a sorted rotated array// function to find the minimum // element's indexfunction findMinIndex(&$arr, $low, $high){ // This condition is needed to // handle the case when array // is not rotated at all if ($high < $low) return 0; // If there is only one element left if ($high == $low) return $low; // Find mid $mid = intval(($low + $high) / 2); // Check if element (mid+1) is // minimum element. Consider // the cases like {3, 4, 5, 1, 2} if ($mid < $high && $arr[$mid + 1] < $arr[$mid]) return ($mid + 1); // Check if mid itself is minimum element if ($mid > $low && $arr[$mid] < $arr[$mid - 1]) return $mid; // Decide whether we need to go // to left half or right half if ($arr[$high] > $arr[$mid]) return findMinIndex($arr, $low, $mid - 1); return findMinIndex($arr, $mid + 1, $high);}// function returns the index of largest// element smaller than equal to 'x' in // 'arr[l...h]'. If no such element exits // in the given range, then it returns l-1. function binary_search(&$arr, $l, $h, $x){ while ($l <= $h) { $mid = intval(($l + $h) / 2); // if 'x' is less than or equal // to arr[mid], then search in // arr[mid+1...h] if ($arr[$mid] <= $x) $l = $mid + 1; // else search in arr[l...mid-1] else $h = $mid - 1; } // required index return $h;}// function to count elements less // than or equal to a given valuefunction countEleLessThanOrEqual(&$arr, $n, $x){ // index of the smallest element // in the array $min_index = findMinIndex($arr, 0, $n - 1); // if largest element smaller than // or equal to 'x' lies in the sorted // range arr[min_index...n-1] if ($x <= $arr[$n - 1]) return (binary_search($arr, $min_index, $n - 1, $x) + 1 - $min_index); // if largest element smaller than or // equal to 'x' lies in the sorted // range arr[0...min_index-1] if (($min_index - 1) >= 0 && $x <= $arr[$min_index - 1]) return ($n - $min_index + binary_search($arr, 0, $min_index - 1, $x) + 1); // else all the elements of // the array are less than 'x' return $n; }// Driver Code$arr = array(6, 10, 12, 15, 2, 4, 5);$n = sizeof($arr);$x = 14;echo "Count = " . countEleLessThanOrEqual($arr, $n, $x);// This code is contributed // by ChitraNayal?> |
Javascript
<script>// Javascript implementation to count elements// less than or equal to a given// value in a sorted rotated array // function to find the minimum // element's index function findMinIndex(arr,low,high) { // This condition is needed to handle // the case when array is not rotated at all if (high < low) return 0; // If there is only one element left if (high == low) return low; // Find mid let mid = Math.floor((low + high) / 2); // Check if element (mid+1) is // minimum element. Consider // the cases like {3, 4, 5, 1, 2} if (mid < high && arr[mid + 1] < arr[mid]) return (mid + 1); // Check if mid itself is minimum element if (mid > low && arr[mid] < arr[mid - 1]) return mid; // Decide whether we need to go to // left half or right half if (arr[high] > arr[mid]) return findMinIndex(arr, low, mid - 1); return findMinIndex(arr, mid + 1, high); } // function returns the index of largest element// smaller than equal to 'x' in 'arr[l...h]'.// If no such element exits in the given range,// then it returns l-1. function binary_search(arr,l,h,x) { while (l <= h) { let mid = Math.floor((l + h) / 2); // if 'x' is less than or equal to arr[mid], // then search in arr[mid+1...h] if (arr[mid] <= x) l = mid + 1; // else search in arr[l...mid-1] else h = mid - 1; } // required index return h; } // function to count elements less than// or equal to a given value function countEleLessThanOrEqual(arr,n,x) { // index of the smallest element in the array let min_index = findMinIndex(arr, 0, n - 1); // if largest element smaller than or // equal to 'x' lies in the sorted // range arr[min_index...n-1] if (x <= arr[n - 1]) return (binary_search(arr, min_index, n - 1, x) + 1 - min_index); // if largest element smaller than or // equal to 'x' lies in the sorted // range arr[0...min_index-1] if ((min_index - 1) >= 0 && x <= arr[min_index - 1]) return (n - min_index + binary_search(arr, 0, min_index - 1, x) + 1); // else all the elements of the array // are less than 'x' return n; } // Driver code let arr=[6, 10, 12, 15, 2, 4, 5]; let n = arr.length; let x = 14; document.write("Count = " + countEleLessThanOrEqual(arr, n, x)); // This code is contributed by rag2127</script> |
Output
Count = 6
Time Complexity: O(logn) as the binary search is used which takes logarithmic time.
The space complexity is O(1).
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
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!
