PROBLEM STATEMENT:
We are given a sorted array and an element. We need to find the number of occurrence of the given element in the array.
QUICK POINTS:
1. We can solve the the problem by finding the index of first occurrence and last occurrence of the element in the array as in this range the given element will occur.
2. The count will be equal to Lastindex-firstindex+1.
ALGORITHM FOR FIRST OCCURANCE:
1. First find the middle element.
2. If the middle element is equal to x, then store the middle index as the answer and search for the element in the left part from the middle index.
3. If the element is greater than the middle element, search for the element in the right part from the middle index.
4. If the element is less than the middle element, search for the element in the left part from the middle index.
5. Continue the process until only one element is left.
ALGORITHM FOR LAST OCCURANCE:
1. First find the middle element.
2. If the middle element is equal to x, then store the middle index as the answer and search for the element in the right part from the middle index.
3. If the element is greater than the middle element, search for the element in the right part from the middle index.
4. If the element is less than the middle element, search for the element in the left part from the middle index.
5. Continue the process until only one element is left.
CODE:
#include <bits/stdc++.h>
using namespace std;
int firstoccurrence(int x,int l,int r,int a[],int firstans)
{
if(r>=l){
int middle=l+(r-l)/2;
if(x==a[middle])
{
firstans= middle;
firstoccurrence(x,l,middle-1,a,firstans);
}
else if(x>a[middle])
firstoccurrence(x,middle+1,r,a,firstans);
else if(x<a[middle])
firstoccurrence(x,l,middle-1,a,firstans);
}
else
return firstans;
}
int lastoccurrence(int x,int l,int r,int a[],int lastans)
{
if(r>=l){
int middle=l+(r-l)/2;
if(x==a[middle])
{
lastans= middle;
lastoccurrence(x,middle+1,r,a,lastans);
}
else if(x>a[middle])
lastoccurrence(x,middle+1,r,a,lastans);
else if(x<a[middle])
lastoccurrence(x,l,middle-1,a,lastans);
}
else
return lastans;
}
int main()
{
int n; //size of array
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int x;
cin>>x;//element to be counted
int firstans=-1,lastans=-1;
int leftindex=firstoccurrence(x,0,n-1,a,firstans);
int rightindex=lastoccurrence(x,0,n-1,a,lastans);
int finalcount=rightindex-leftindex+1;
cout<<finalcount;
return 0;
}
INPUT:
10
1 2 2 2 2 6 7 9 11 12
2
OUTPUT:
4
0 Comments