Count Number of Occurrences in a Sorted Array

Problem Statement

In the “Count Number of Occurrences in a Sorted Array” problem, we have given a sorted array. Count the number of occurrences or frequency in a sorted array of X where X is an integer.

Example

Input

13

1 2 2 2 2 3 3 3 4 4 4 5 5

3

Output

3

Approach 1 for Count Number of Occurrences in a Sorted Array

1. Simply do a modified binary search such that
2. Find the first occurrence of X like this:

1.  Check if the middle element of the array is equal to X.
2. If the equal or greater element is at mid then reduce the partition from start to mid-1. As we will have the first occurrence on the left side of mid of array then.
3. If the middle element is smaller then we will check in the right side of the middle element as the array is sorted.
4. Return the first occurrence.

3. Now similarly find the last occurrence of X in the array by doing

1. Check if the middle element of the array is equal to X
2. If the equal or smaller element is at mid then increase the partition from mid+1 to high. As we will have the last occurrence on the right side of mid of array then.
3. Else search in the left side of array
4. return the last occurrence

4. Now the number of occurrences is simply the last occurrence – first occurrence+1.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int first_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int first = INT_MAX;
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found then check the left part for further occurence
    {
      if(mid < first)
      first = mid;
      high = mid-1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return first;
}
int last_occurence(int arr[],int N,int X)
{
  int low = 0 , high = N-1;
  int last = INT_MIN;
  
  while(low <= high)
  {
    int mid = low + ((high-low)>>1);
    if(arr[mid] == X) //if found check in right subpart for last occurence
    {
      if(mid > last)
      last = mid;
      low = mid+1;
    }
    else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
      low = mid + 1;
    else if (arr[mid] > X)//if middle element is larger than X check in left subpart
      high = mid - 1;
  }
  
  return last;
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
  int X; // number whose count is to be found out
  cin >> X;
  int count = 0; //initially its count is zero
  int last = last_occurence(a,n,X);
  if(last != INT_MIN)
    count += last;
  
  int first = first_occurence(a,n,X);
  if(first != INT_MAX)
    count -= first;
  cout<<last-first+1<<endl;  
  return 0;
}

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static int first_occurence(int arr[],int N,int X)
    {
      int low = 0 , high = N-1;
      int first = 10000000;
      while(low <= high)
      {
        int mid = low + ((high-low)>>1);
        if(arr[mid] == X) //if found then check the left part for further occurence
        {
          if(mid < first)
          first = mid;
          high = mid-1;
        }
        else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
          low = mid + 1;
        else if (arr[mid] > X)//if middle element is larger than X check in left subpart
          high = mid - 1;
      }
      return first;
    }
    public static int last_occurence(int arr[],int N,int X)
    {
      int low = 0 , high = N-1;
      int last = -1;
      while(low <= high)
      {
        int mid = low + ((high-low)>>1);
        if(arr[mid] == X) //if found check in right subpart for last occurence
        {
          if(mid > last)
          last = mid;
          low = mid+1;
        }
        else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
          low = mid + 1;
        else if (arr[mid] > X)//if middle element is larger than X check in left subpart
          high = mid - 1;
      }
      return last;
    }
    public static int abs(int x)
    {
        if(x<0)
            x=x*-1;
        return x;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = sr.nextInt(); // number whose count is to be found out
        int count = 0; //initially its count is zero
        int last = last_occurence(arr,n,X);
        if(last != -1)
          count += last;
        int first = first_occurence(arr,n,X);
        if(first != 10000000)
          count -= first;
        System.out.println(last-first+1);
    }
}

8
1 1 2 2 2 3 4 5 
2

3

Approach 2 for Count Number of Occurrences in a Sorted Array

1. Simply do the same approach as algorithm 1 but using upper_bound() and lower_bound functions.
2. Calculate the last occurrence using upper_bound() and first occurrence via lower_bound() functions.
3. Number of occurrences is simply the index obtained by upper_bound() –
4. lower_bound().

Low_bound(), Upper_bound are Standard Template Library(STL) functions.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    count  = upper_bound(a,a+n,X) - lower_bound(a,a+n,X); 
    cout<<count;
    return 0;
}

8
1 1 2 2 2 3 4 5 
4

1

Approach 3 for Count Number of Occurrences in a Sorted Array

1. Simply run a loop.
2. If we get an element equal to X start increasing the count
3. Till we see X increase the count and as soon as we get a number different from X then we display the obtained count as it is a sorted array.

Explanation

Run one loop from beginning to the end of the array and check for if x==a[i] then increase the counts. Here let’s take an example. a[]={1, 2, 2, 2, 3, 4} and x=2 then the count of x is 3. So, our final answer is 3.

Implementation

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int X; // number whose count is to be found out
    cin >> X;
    int count = 0; //initially its count is zero
    for(int i=0;i<n;i++)
    if(a[i]==X)
      count++;
    cout<<count;
    return 0;
}

Java Program

import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = sr.nextInt(); // number whose count is to be found out
        int count = 0; //initially its count is zero
        for(int i=0;i<n;i++)
        if(arr[i]==X)
          count++;
        System.out.println(count);
    }
}

8
1 1 2 2 2 3 4 5 
1

2

Complexity Analysis for Count Number of Occurrences in a Sorted Array

Time Complexity – O(N) because we traverse the whole array and count the frequency of x.
Space Complexity – O(1) because we don’t use any auxiliary space here.

References