Find repeating element in a sorted array of size n
Given a sorted an 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 an array using a for a loop.
- For each element in the array, traverse the remaining part of the an 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:
# Python3 program to find the just repeating element in an
# an array of size n and elements from range 1 to n-1.
# Returns second appearance of a repeating element
# The function/method assumes that an 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)
Output
4
An efficient method is to use Floyd’s Tortoise and Hare algorithm.
# Python program to find the just repeating element in an
# 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)
Output
3