Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Examples 
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation 
2.2.1.
Complexity Analysis 
3.
Binary Search
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Complexity Analysis 
4.
Frequently Asked Questions
4.1.
What is binary search?
4.2.
How do you know how many times a number repeats in an array?
4.3.
Why are there time complexity differences in the two approaches discussed above?
4.4.
Why is the space complexity the same for both approaches?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Counting repeated elements in a sorted array of consecutive elements is an array searching problem. It is a well-known practice problem for learning problem-solving 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.
     
  • Variable-length 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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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 Searchtime 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 AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!

Previous article
Square Root using binary search
Next article
Find Element in a Sorted Array whose Frequency is Greater than or Equal to n/2
Live masterclass