Count number of occurrences (or frequency) in a sorted array
Given a sorted array arr[] of size N and a number X, you need to find the number of occurrences of X in given array.
Note: Expected time complexity is O(log(n))
Examples:
Input: N = 7, X = 2, Arr[] = {1, 1, 2, 2, 2, 2, 3}
Output: 4
Explanation: 2 occurs 4 times in the given array.Input: N = 7, X = 4, arr[] = {1, 1, 2, 2, 2, 2, 3}
Output: 0
Explanation: 4 is not present in the given array.
Count number of occurrences (or frequency) in a sorted array using Linear Search:
Iterate over the given array and check if current element is equals to x, increment count or res variable.
Below is the implementation of the above approach:
#include<iostream>
using namespace std;
// Returns number of times x occurs in arr[0..n-1]
int countOccurrences(int arr[], int n, int x)
{
int res = 0;
for (int i = 0; i < n; i++)
if (x == arr[i])
res++;
return res;
}
// Driver code
int main()
{
int arr[] = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
cout<< countOccurrences(arr, n, x);
return 0;
}
// Java program to count occurrences
// of an element
class Main
{
// Returns number of times x occurs in arr[0..n-1]
static int countOccurrences(int arr[], int n, int x)
{
int res = 0;
for (int i=0; i<n; i++)
if (x == arr[i])
res++;
return res;
}
public static void main(String args[])
{
int arr[] = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };
int n = arr.length;
int x = 2;
System.out.println(countOccurrences(arr, n, x));
}
}
# Python3 program to count
# occurrences of an element
# Returns number of times x
# occurs in arr[0..n-1]
def countOccurrences(arr, n, x):
res = 0
for i in range(n):
if x == arr[i]:
res += 1
return res
# Driver code
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
n = len(arr)
x = 2
print(countOccurrences(arr, n, x))
<script>
// Javascript program to count occurrences
// of an element
// Returns number of times x occurs in arr[0..n-1]
function countOccurrences(arr,n,x)
{
let res = 0;
for (let i=0; i<n; i++)
{
if (x == arr[i])
res++;
}
return res;
}
arr=[1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8]
let n = arr.length;
let x = 2;
document.write(countOccurrences(arr, n, x));
// This code is contributed by avanitrachhadiya2155
</script>
<?php
// PHP program to count occurrences
// of an element
// Returns number of times x
// occurs in arr[0..n-1]
function countOccurrences($arr, $n, $x)
{
$res = 0;
for ($i = 0; $i < $n; $i++)
if ($x == $arr[$i])
$res++;
return $res;
}
// Driver code
$arr = array(1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 );
$n = count($arr);
$x = 2;
echo countOccurrences($arr,$n, $x);
// This code is contributed by Sam007
?>
Output
4
Time Complexity: O(n)
Auxiliary Space: O(1), as no extra space is used
Count number of occurrences (or frequency) in a sorted array using Binary Search:
To count the occurrences of a given element x in a sorted array arr[]. It achieves this by performing the following steps:
Finding the first occurrence:
- It uses a binary search-based function firstOcc to find the index of the first occurrence of x in the array.
- If x is not found, firstOcc returns -1.
Finding the last occurrence:
- If the first occurrence is found, another binary search-based function lastOcc is used to find the index of the last occurrence of x.
Calculating the count:
- If both the first and last occurrences are found, the difference between their indices + 1 gives the total number of occurrences of x.
- If either the first or last occurrence is not found, the count would be 0.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to find the first occurrence of an element in a
// sorted array
int firstOcc(int* arr, int l, int h, int x)
{
if (h >= l) {
int mid = (l + h) / 2;
// Check if the element is present at the middle or
// if the element is present in the left half (if
// the element is greater than the middle element)
if ((mid == 0 || x > arr[mid - 1])
&& arr[mid] == x) {
return mid;
}
else if (x > arr[mid]) {
// Search in the right half
return firstOcc(arr, (mid + 1), h, x);
}
else {
// Search in the left half
return firstOcc(arr, l, (mid - 1), x);
}
}
return 0;
}
// Function to find the last occurrence of an element in a
// sorted array
int lastOcc(int arr[], int n, int l, int h, int x)
{
if (h >= l) {
int mid = (l + h) / 2;
// Check if the element is present at the middle or
// if the element is present in the right half (if
// the element is smaller than the middle element)
if ((mid == n - 1 || x < arr[mid + 1])
&& arr[mid] == x) {
return mid;
}
else if (x < arr[mid]) {
// Search in the left half
return lastOcc(arr, n, l, (mid - 1), x);
}
else {
// Search in the right half
return lastOcc(arr, n, (mid + 1), h, x);
}
}
return -1;
}
// Function to count the occurrences of an element in a
// sorted array
int countOccurrences(int arr[], int n, int x)
{
// Find the first and last occurrences of the element
int idxFirst = firstOcc(arr, 0, n - 1, x);
// If the element does not exist, return -1
if (idxFirst == -1) {
return -1;
}
int idxLast = lastOcc(arr, n, idxFirst, n - 1, x);
// Return the difference between the last and first
// occurrences + 1 to get the total count
return idxLast - idxFirst + 1;
}
int main()
{
int arr[] = { 1, 1, 2, 2, 2, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
int occurrences = countOccurrences(arr,n, x);
cout << "Number of occurrences of " << x << ": "
<< occurrences << std::endl;
return 0;
}
public class Main {
// Function to find the first occurrence of an element in a sorted array
static int firstOcc(int[] arr, int l, int h, int x) {
if (h >= l) {
int mid = (l + h) / 2;
// Check if the element is present at the middle or
// if the element is present in the left half (if
// the element is greater than the middle element)
if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x) {
return mid;
} else if (x > arr[mid]) {
// Search in the right half
return firstOcc(arr, mid + 1, h, x);
} else {
// Search in the left half
return firstOcc(arr, l, mid - 1, x);
}
}
return -1;
}
// Function to find the last occurrence of an element in a sorted array
static int lastOcc(int[] arr, int n, int l, int h, int x) {
if (h >= l) {
int mid = (l + h) / 2;
// Check if the element is present at the middle or
// if the element is present in the right half (if
// the element is smaller than the middle element)
if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x) {
return mid;
} else if (x < arr[mid]) {
// Search in the left half
return lastOcc(arr, n, l, mid - 1, x);
} else {
// Search in the right half
return lastOcc(arr, n, mid + 1, h, x);
}
}
return -1;
}
// Function to count the occurrences of an element in a sorted array
static int countOccurrences(int[] arr, int n, int x) {
// Find the first and last occurrences of the element
int idxFirst = firstOcc(arr, 0, n - 1, x);
// If the element does not exist, return -1
if (idxFirst == -1) {
return -1;
}
int idxLast = lastOcc(arr, n, idxFirst, n - 1, x);
// Return the difference between the last and first
// occurrences + 1 to get the total count
return idxLast - idxFirst + 1;
}
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 2, 2, 3};
int n = arr.length;
int x = 2;
int occurrences = countOccurrences(arr, n, x);
System.out.println("Number of occurrences of " + x + ": " + occurrences);
}
}
# Function to find the first occurrence of an element in a
# sorted array
def firstOcc(arr, l, h, x):
if h >= l:
mid = (l + h) // 2
# Check if the element is present at the middle or
# if the element is present in the left half (if
# the element is greater than the middle element)
if (mid == 0 or x > arr[mid - 1]) and arr[mid] == x:
return mid
elif x > arr[mid]:
# Search in the right half
return firstOcc(arr, mid + 1, h, x)
else:
# Search in the left half
return firstOcc(arr, l, mid - 1, x)
return -1
# Function to find the last occurrence of an element in a
# sorted array
def lastOcc(arr, n, l, h, x):
if h >= l:
mid = (l + h) // 2
# Check if the element is present at the middle or
# if the element is present in the right half (if
# the element is smaller than the middle element)
if (mid == n - 1 or x < arr[mid + 1]) and arr[mid] == x:
return mid
elif x < arr[mid]:
# Search in the left half
return lastOcc(arr, n, l, mid - 1, x)
else:
# Search in the right half
return lastOcc(arr, n, mid + 1, h, x)
return -1
# Function to count the occurrences of an element in a
# sorted array
def countOccurrences(arr, n, x):
# Find the first and last occurrences of the element
idxFirst = firstOcc(arr, 0, n - 1, x)
# If the element does not exist, return -1
if idxFirst == -1:
return -1
idxLast = lastOcc(arr, n, idxFirst, n - 1, x)
# Return the difference between the last and first
# occurrences + 1 to get the total count
return idxLast - idxFirst + 1
if __name__ == "__main__":
arr = [1, 1, 2, 2, 2, 2, 3]
n = len(arr)
x = 2
occurrences = countOccurrences(arr, n, x)
print("Number of occurrences of", x, ":", occurrences)
// Function to find the first occurrence of an element in a sorted array
function firstOcc(arr, l, h, x) {
if (h >= l) {
let mid = Math.floor((l + h) / 2);
// Check if the element is present at the middle or
// if the element is present in the left half (if
// the element is greater than the middle element)
if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x) {
return mid;
} else if (x > arr[mid]) {
// Search in the right half
return firstOcc(arr, mid + 1, h, x);
} else {
// Search in the left half
return firstOcc(arr, l, mid - 1, x);
}
}
return -1;
}
// Function to find the last occurrence of an element in a sorted array
function lastOcc(arr, n, l, h, x) {
if (h >= l) {
let mid = Math.floor((l + h) / 2);
// Check if the element is present at the middle or
// if the element is present in the right half (if
// the element is smaller than the middle element)
if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x) {
return mid;
} else if (x < arr[mid]) {
// Search in the left half
return lastOcc(arr, n, l, mid - 1, x);
} else {
// Search in the right half
return lastOcc(arr, n, mid + 1, h, x);
}
}
return -1;
}
// Function to count the occurrences of an element in a sorted array
function countOccurrences(arr, n, x) {
// Find the first and last occurrences of the element
let idxFirst = firstOcc(arr, 0, n - 1, x);
// If the element does not exist, return -1
if (idxFirst == -1) {
return -1;
}
let idxLast = lastOcc(arr, n, idxFirst, n - 1, x);
// Return the difference between the last and first
// occurrences + 1 to get the total count
return idxLast - idxFirst + 1;
}
// Main function
function main() {
let arr = [1, 1, 2, 2, 2, 2, 3];
let n = arr.length;
let x = 2;
let occurrences = countOccurrences(arr, n, x);
console.log("Number of occurrences of " + x + ": " + occurrences);
}
// Call the main function
main();
Output
Number of occurrences of 2: 4
Time Complexity: O(log(n))
Auxiliary Space: O(1)
Contact Us