Introduction
Counting repeated elements in a sorted array of consecutive elements is an array searching problem. It is a wellknown practice problem for learning problemsolving and time complexity optimization. It had also been asked by the Amazon and Uber interview panel for the roles of SDE intern.
In this article, weâ€™ll use two methods to solve the problem of counting repeated elements in a sorted array of consecutive elements; the first is by brute force, and the second is by using Binary Search.
Problem Statement
In the problem of counting repeated elements in a sorted array of consecutive elements, we are given a sorted array A[] of size n. We have to write a program to find the count of elements repeated in our array A[] and discuss its time complexity.
Sample Examples
Example 1
Input: A[] =
Output:
Repeated Element: 2
Number of occurrences: 6
Explanation: 2 is the only repeating element that appears 6 times.
Example 2
Input: P[] =
Output:
Repeated Element: 10
Number of occurrences: 2
Explanation: 10 is the only repeating element that appears 2 times.
Brute Force Approach
The simplest method would be to count the occurrences of each element.
Algorithm

We take an integer array a[] whose elements are consecutive numbers, here one number is repeated among those consecutive numbers.

Variablelength stores the length of the array a[].

Function findingRepeat(int arr[], int n) takes an array, and its length as input and displays repeated elements' repeated element value and length.

Take the initial count of the element as 0.

Now starting from index i=0 to i<n. If arr[i]==arr[i+1]. Increment count. Store element in variable value.

At the end of the loop, increment the count by 1 for the last element.

Display element, which is repeated as value.
 Display the number of repetitions as a count.
Implementation
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[]={ 2,3,4,5,5,5,6,7,8 };
int length=sizeof(a)/sizeof(a[0]);
int ans=0; //count of element
int element=0;
for(int i=0; i<length; i++)
{
if(a[i]==a[i+1])
{
ans++;
element=a[i];
}
}
ans++;
cout<<"Repeated Element: "<<element;
cout<<endl<<"Number of occurrences: "<<ans;
return 0;
}
Output
Complexity Analysis
Time Complexity: For each iteration, we run a loop so the time complexity is O(n).
Space Complexity: We are using a fixed number of extra variables, Space Complexity is O(1).