Find the only repeating element in a sorted array of size n
Given a sorted array of n elements containing elements in range from 1 to n-1 i.e. one element occurs twice, the task is to find the repeating element in an array.
Examples :
Input : arr[] = { 1, 2 , 3 , 4 , 4}
Output : 4
Input : arr[] = { 1 , 1 , 2 , 3 , 4}
Output : 1
Brute Force:
- Traverse the input array using a for a loop.
- For each element in the array, traverse the remaining part of the array using another for loop.
- For each subsequent element, check if it is equal to the current element.
- If a match is found, return the current element.
- If no match is found, continue with the next element in the outer loop.
- If the outer loop completes without finding a match, return -1 to indicate that there is no repeating element in the array.
Below is the implementation of the above approach:
// C++ program to find the only repeating element in an
// array of size n and elements from range 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
// Returns index of second appearance of a repeating element
// The function assumes that array elements are in range from
// 1 to n-1.
int FindRepeatingElement(int arr[], int size){
for(int i=0; i<size; i++){
for(int j=i+1; j<size; j++){
if(arr[i] == arr[j])
return i;
}
}
return -1;
}
// Driver code
int main()
{
int arr[] = {1, 2 , 3 , 4 , 4};
int n = sizeof(arr) / sizeof(arr[0]);
int index = FindRepeatingElement(arr, n);
if (index != -1)
cout << arr[index];
return 0;
}
import java.util.*;
public class Main {
// Returns index of second appearance of a repeating element
// The function assumes that array elements are in range from
// 1 to n-1.
public static int findRepeatingElement(int arr[], int size){
for(int i=0; i<size; i++){
for(int j=i+1; j<size; j++){
if(arr[i] == arr[j])
return i;
}
}
return -1;
}
// Driver code
public static void main(String[] args) {
int arr[] = {1, 2 , 3 , 4 , 4};
int n = arr.length;
int index = findRepeatingElement(arr, n);
if (index != -1)
System.out.println(arr[index]);
}
}
# Python3 program to find the only repeating element in an
# array of size n and elements from range 1 to n-1.
# Returns second appearance of a repeating element
# The function assumes that array elements are in range from
# 1 to n-1.
def FindRepeatingElement(arr, size):
for i in range(size):
for j in range(i+1, size):
if arr[i] == arr[j]:
return arr[i]
return -1
# Driver code
if __name__ == '__main__':
arr = [1, 2, 3, 4, 4]
n = len(arr)
element = FindRepeatingElement(arr, n)
if element != -1:
print(element)
using System;
public class Program
{
// Returns index of second appearance of a repeating element
// The function assumes that array elements are in range from
// 1 to n-1.
public static int FindRepeatingElement(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = i + 1; j < size; j++)
{
if (arr[i] == arr[j])
{
return i;
}
}
}
return -1;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 4 };
int n = arr.Length;
int index = FindRepeatingElement(arr, n);
if (index != -1)
{
Console.WriteLine(arr[index]);
}
}
}
// JavaScript program to find the only repeating element in an
// array of size n and elements from range 1 to n-1.
// Returns index of second appearance of a repeating element
// The function assumes that array elements are in range from
// 1 to n-1.
function FindRepeatingElement(arr, size)
{
for(let i=0; i<size; i++)
{
for(let j=i+1; j<size; j++)
{
if(arr[i] == arr[j])
return i;
}
}
return -1;
}
// Driver code
let arr = [1, 2 , 3 , 4 , 4];
let n = arr.length;
let index = FindRepeatingElement(arr, n);
if (index != -1)
console.log(arr[index]);
// This code is contributed by akashish__
Output
4
Time Complexity: O(N^2)
Auxiliary Space: O(1)
An efficient method is to use Floyd’s Tortoise and Hare algorithm.
// C++ program to find the only repeating element in an
// array of size n and elements from range 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
// Returns the repeating element in the array
// The function assumes that array elements are in range from
// 1 to n-1.
int FindRepeatingElement(int arr[], int size){
for(int i = 0; i < size; i++){
if(arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else
return abs(arr[i]);
}
return -1;
}
// Driver code
int main()
{
int arr[] = {1,3,3,4,5,6,7,8};
int n = sizeof(arr) / sizeof(arr[0]);
int repeatingElement = FindRepeatingElement(arr, n);
cout << repeatingElement;
return 0;
}
class Test
{
// Returns the repeating element in the array
// The function assumes that array elements are in range from
// 1 to n-1.
static int findRepeatingElement(int arr[]){
int tortoise = arr[0];
int hare = arr[0];
// Phase 1: Finding intersection point of Tortoise and Hare
do {
tortoise = arr[tortoise];
hare = arr[arr[hare]];
} while(tortoise != hare);
// Phase 2: Finding the entrance to the cycle
tortoise = arr[0];
while(tortoise != hare){
tortoise = arr[tortoise];
hare = arr[hare];
}
return hare;
}
// Driver method
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 3, 4, 5};
int repeatingElement = findRepeatingElement(arr);
System.out.println(repeatingElement);
}
}
# Python program to find the only repeating element in an
# array of size n and elements from range 1 to n-1
def findRepeatingElement(arr):
tortoise = arr[0]
hare = arr[0]
# Phase 1: Finding intersection point of Tortoise and Hare
while True:
tortoise = arr[tortoise]
hare = arr[arr[hare]]
if tortoise == hare:
break
# Phase 2: Finding the entrance to the cycle
tortoise = arr[0]
while tortoise != hare:
tortoise = arr[tortoise]
hare = arr[hare]
return hare
# Driver code
arr = [1, 2, 3, 3, 4, 5]
repeatingElement = findRepeatingElement(arr)
print(repeatingElement)
// C# program to find the only repeating
// element in an array of size n and
// elements from range 1 to n-1.
using System;
class Test
{
// Returns index of second appearance of a
// repeating element. The function assumes that
// array elements are in range from 1 to n-1.
static int findRepeatingElement(int []arr, int low,
int high)
{
// low = 0 , high = n-1;
if (low > high)
return -1;
int mid = (low + high) / 2;
// Check if the mid element
// is the repeating one
if (arr[mid] != mid + 1)
{
if (mid > 0 && arr[mid]==arr[mid-1])
return mid;
// If mid element is not at its position
// that means the repeated element is in left
return findRepeatingElement(arr, low, mid-1);
}
// If mid is at proper position
// then repeated one is in right.
return findRepeatingElement(arr, mid+1, high);
}
// Driver method
public static void Main()
{
int []arr = {1, 2, 3, 3, 4, 5};
int index = findRepeatingElement(arr, 0, arr.Length-1);
if (index != -1)
Console.Write(arr[index]);
}
}
// This code is contributed by Nitin Mittal.
<script>
// JavaScript program to find the only repeating element in an
// array of size n and elements from range 1 to n-1.
// Returns index of second appearance of a repeating element
// The function assumes that array elements are in range from
// 1 to n-1.
function findRepeatingElement(arr, low, high)
{
// low = 0 , high = n-1;
if (low > high) return -1;
var mid = parseInt((low + high) / 2);
// Check if the mid element is the repeating one
if (arr[mid] != mid + 1)
{
if (mid > 0 && arr[mid] == arr[mid - 1]) return mid;
// If mid element is not at its position that means
// the repeated element is in left
return findRepeatingElement(arr, low, mid - 1);
}
// If mid is at proper position then repeated one is in
// right.
return findRepeatingElement(arr, mid + 1, high);
}
// Driver code
var arr = [1, 2, 3, 3, 4, 5];
var n = arr.length;
var index = findRepeatingElement(arr, 0, n - 1);
if (index != -1) document.write(arr[index]);
// This code is contributed by rdtank.
</script>
<?php
// PHP program to find the only
// repeating element in an array
// of size n and elements from
// range 1 to n-1.
// Returns index of second
// appearance of a repeating
// element. The function assumes
// that array elements are in
// range from 1 to n-1.
function findRepeatingElement($arr,
$low,
$high)
{
// low = 0 , high = n-1;
if ($low > $high)
return -1;
$mid = floor(($low + $high) / 2);
// Check if the mid element
// is the repeating one
if ($arr[$mid] != $mid + 1)
{
if ($mid > 0 && $arr[$mid] ==
$arr[$mid - 1])
return $mid;
// If mid element is not at
// its position that means
// the repeated element is in left
return findRepeatingElement($arr, $low,
$mid - 1);
}
// If mid is at proper position
// then repeated one is in right.
return findRepeatingElement($arr, $mid + 1,
$high);
}
// Driver code
$arr = array(1, 2, 3, 3, 4, 5);
$n = sizeof($arr);
$index = findRepeatingElement($arr, 0,
$n - 1);
if ($index != -1)
echo $arr[$index];
// This code is contributed
// by nitin mittal.
?>
Output
3
Time Complexity : O(log n)
Space Complexity: O(1)
Contact Us