Count of only Repeated Element in a Sorted Array of Consecutive Elements

Binary Search

"How do we improve time complexity?" is now the critical question. Can we reduce the time complexity of searching because it is the most important operation in the problem? Let's give it some thought!

A naive approach would scan the entire array and return if an element appears twice. This method takes O(n) time. So to improve the time complexity of the problem, we try another approach.

Algorithm

Binary Search is an efficient method.

1. Determine whether the middle element is the repeating one.
2. If not, check to see if the middle element is in the correct position; if so, begin looking for repeating elements on the right.
3. If not, the repeating one will be on the left.

Implementation

#include <bits/stdc++.h>
using namespace std;

pair<int, int> Find(vector<int>& a)
{
	if (a.size() == 0)
	return {0, 0};
	int f = 0;
	int l = a.size() - 1;
	while (f < l)
	{
		int m = (f + l) / 2;
		if (a[m] >= m + a[0])
		f = m + 1;
		else
		l = m;
	}
	return {a[f], a.size() - (a[a.size() - 1] - a[0])};
}

int main()
{
	vector<int> v{ 1, 2, 3, 4, 4, 4, 5, 6 };
	pair<int, int>p = Find(v);
	cout << "Repeated Element: " << p.first<<endl << "Number of occurences: " << p.second;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output 

Complexity Analysis 

Time Complexity: O(logn), as the given array is sorted, we can use binary search which reduces the time complexity to O(log n). 

Space Complexity: We are using a fixed number of extra variables, space the complexity is O(1).

Read More - Time Complexity of Sorting Algorithms and  Rabin Karp Algorithm

Frequently Asked Questions

What is binary search?

The binary search is a searching algorithm that divides the search interval in half repeatedly in a sorted array. The idea behind binary search is to use the array's sorted information to reduce the time complexity to O(log n).

How do you know how many times a number repeats in an array?

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

Why are there time complexity differences in the two approaches discussed above?

In the above approaches, the time complexity of the brute force approach is O(N) and in the binary search approach is O(log N), there is a difference in time complexity because we are using linear search in the brute force approach and the binary search in other. The search got optimized in doing so thus resulting in optimized time complexity.

Why is the space complexity the same for both approaches?

We are using a fixed number of extra variables, that’s why the space complexity of both approaches is O(1).

Conclusion

This article extensively discussed the problem of counting repeated elements in a sorted array of consecutive elements.

We hope that this blog has helped you enhance your knowledge regarding the array searching problem. After reading about the problem on the count of the only repeated elements in a sorted array of consecutive elements, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. To learn, see Binary Search, time complexity, and Complexity Analysis.

Recommended Problem - Merge K Sorted Arrays

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! 

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations. 

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!