Count of only repeated element in a sorted array of consecutive elements
Given a sorted array of consecutive elements. The array has only one element repeated many times. The task is to find the length of the sequence of the repeated elements
Examples:
Input: arr[] = {1, 2, 3, 4, 4, 4, 5, 6}
Output: 4 3
Repeated element is 4 and it appears 3 timesInput: arr[] = {4, 4, 4, 4, 4}
Output: 4 5Input: arr[] = {6, 7, 8, 9, 10, 10, 11}
Output: 10 2Input: arr[] = {6, 7, 8, 9, 10, 10, 10}
Output: 10 3
Count of only repeated elements in a sorted array of consecutive elements using binary search:
To solve the problem follow the below idea:
We need to find two things:
- To find the number of times the element repeats:
- Suppose there is no repeated element for given array, then the least element will be at arr[0] and highest element will be at arr[n-1].
- Now each time an element is repeated, the highest element will decrease by 1 each time.
- Based on this idea, since the array is sorted and max-difference of two adjacent elements is 1, then:
count of unique elements = arr[n-1] – arr[0]
Therefore, length of the repeated element = n – count of unique elements
= n – (array[n-1] – array[0])
- To find value of repeated element:
- To find the repeated value, we can use Binary Search
Below is the implementation of the above approach:
C++
// C++ program to find the only repeated element // and number of times it appears #include <bits/stdc++.h> using namespace std; // Assumptions : vector a is sorted, max-difference // of two adjacent elements is 1 pair< int , int > sequence( const vector< int >& a) { if (a.size() == 0) return { 0, 0 }; int s = 0; int e = a.size() - 1; while (s < e) { int m = (s + e) / 2; // if a[m] = m + a[0], there is no // repeating character in [s..m] if (a[m] >= m + a[0]) s = m + 1; // if a[m] < m + a[0], there is a // repeating character in [s..m] else e = m; } return { a[s], a.size() - (a[a.size() - 1] - a[0]) }; } // Driver code int main() { pair< int , int > p = sequence({ 1, 2, 3, 4, 4, 4, 5, 6 }); // Function call cout << "Repeated element is " << p.first << ", it appears " << p.second << " times" ; return 0; } |
Java
// Java program to find the only repeated element // and number of times it appears import java.awt.Point; import java.util.Arrays; import java.util.Vector; class Test { // Assumptions : vector a is sorted, max-difference // of two adjacent elements is 1 static Point sequence(Vector<Integer> a) { if (a.size() == 0 ) return new Point( 0 , 0 ); int s = 0 ; int e = a.size() - 1 ; while (s < e) { int m = (s + e) / 2 ; // if a[m] = m + a[0], there is no // repeating character in [s..m] if (a.get(m) >= m + a.get( 0 )) s = m + 1 ; // if a[m] < m + a[0], there is a // repeating character in [s..m] else e = m; } return new Point( a.get(s), a.size() - (a.get(a.size() - 1 ) - a.get( 0 ))); } // Driver code public static void main(String args[]) { Integer array[] = new Integer[] { 1 , 2 , 3 , 4 , 4 , 4 , 5 , 6 }; // Function call Point p = sequence( new Vector<>(Arrays.asList(array))); System.out.println( "Repeated element is " + p.x + ", it appears " + p.y + " times" ); } } |
Python3
# Python3 program to find the # only repeated element and # number of times it appears # Assumptions : vector a is sorted, # max-difference of two adjacent # elements is 1 def sequence(a): if ( len (a) = = 0 ): return [ 0 , 0 ] s = 0 e = len (a) - 1 while (s < e): m = (s + e) / / 2 # if a[m] = m + a[0], there is no # repeating character in [s..m] if (a[m] > = m + a[ 0 ]): s = m + 1 # if a[m] < m + a[0], there is a # repeating character in [s..m] else : e = m return [a[s], len (a) - ( a[ len (a) - 1 ] - a[ 0 ])] # Driver code if __name__ = = "__main__" : p = sequence([ 1 , 2 , 3 , 4 , 4 , 4 , 5 , 6 ]) # Function call print ( "Repeated element is" , p[ 0 ], ", it appears" , p[ 1 ], "times" ) # This code is contributed by Mohit Kumar |
C#
// C# program to find the only repeated element // and number of times it appears using System; using System.Collections.Generic; public class Point { public int first, second; public Point( int first, int second) { this .first = first; this .second = second; } } public class Test { // Assumptions : vector a is sorted, max-difference // of two adjacent elements is 1 static Point sequence(List< int > a) { if (a.Count == 0) return new Point(0, 0); int s = 0; int e = a.Count - 1; while (s < e) { int m = (s + e) / 2; // if a[m] = m + a[0], there is no // repeating character in [s..m] if (a[m] >= m + a[0]) s = m + 1; // if a[m] < m + a[0], there is a // repeating character in [s..m] else e = m; } return new Point(a[s], a.Count - (a[a.Count - 1] - a[0])); } // Driver code public static void Main(String[] args) { int [] array = new int [] { 1, 2, 3, 4, 4, 4, 5, 6 }; Point p = sequence( new List< int >(array)); // Function call Console.WriteLine( "Repeated element is " + p.first + ", it appears " + p.second + " times" ); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find the only repeated element // and number of times it appears // Assumptions : vector a is sorted, max-difference // of two adjacent elements is 1 function sequence(a) { if (a.length == 0) return [0, 0] let s = 0 let e = a.length - 1 while (s < e) { let m = Math.floor((s + e) / 2); // if a[m] = m + a[0], there is no // repeating character in [s..m] if (a[m] >= m + a[0]) s = m + 1 // if a[m] < m + a[0], there is a // repeating character in [s..m] else e = m } return [a[s], a.length - ( a[a.length - 1] - a[0])] } // Driver method let p = sequence([1, 2, 3, 4, 4, 4, 5, 6]) document.write( "Repeated element is " + p[0]+ ", it appears " + p[1]+ " times" ) // This code is contributed by patel2127 </script> |
Repeated element is 4, it appears 3 times
Time Complexity: O(log N)
Auxiliary Space: O(1)