Table of Contents

## 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:

- Check if the middle element of the array is equal to X.
- 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.
- If the middle element is smaller then we will check in the right side of the middle element as the array is sorted.
- Return the first occurrence.

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

- Check if the middle element of the array is equal to X
- 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.
- Else search in the left side of array
- 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; }

#### Java Program

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

### Complexity Analysis for Count Number of Occurrences in a Sorted Array

**Time Complexity – O(logN) **where N is the size of the array. Here we use a binary search which leads us to logN time complexity.

**Space Complexity – O(1) **because we don’t use any auxiliary space here.

## Approach 2 for Count Number of Occurrences in a Sorted Array

- Simply do the same approach as algorithm 1 but using upper_bound() and lower_bound functions.
- Calculate the last occurrence using upper_bound() and first occurrence via lower_bound() functions.
- Number of occurrences is simply the index obtained by upper_bound() –
- 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

### Complexity Analysis for Count Number of Occurrences in a Sorted Array

**Time Complexity – O(logN) **where N is the size of the array. Here we use inbuild STL function which has logN time complexity.

**Space Complexity – O(1) **because we don’t use any auxiliary space here.

## Approach 3 for Count Number of Occurrences in a Sorted Array

- Simply run a loop.
- If we get an element equal to X start increasing the count
- 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.