Tutorialspoint.dev

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



A naive approach is to scan the whole array and check if an element occurs twice, then return. This approach takes O(n) time.

An efficient method is to use Binary Search .
1- Check if the middle element is the repeating one.
2- If not then check if the middle element is at proper position if yes then start searching repeating element in right.
3- Otherwise the repeating one will be in left.

C/C++

// 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 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 code
int main()
{
    int  arr[] = {1, 2, 3, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = findRepeatingElement(arr, 0, n-1);
    if (index != -1)
        cout << arr[index];
    return 0;
}

Java

// Java program to find the only repeating element in an
// array of size n and elements from range 1 to n-1.
  
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(String[] args) 
    {
        int  arr[] = {1, 2, 3, 3, 4, 5};
        int index = findRepeatingElement(arr, 0, arr.length-1);
        if (index != -1)
            System.out.println(arr[index]);
    }
}

Python

# Python 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.
def findRepeatingElement(arr, low, high):
  
    # low = 0 , high = n-1
    if low > high:
        return -1
  
    mid = (low + high) / 2
  
    # Check if the mid element is the repeating one
    if (arr[mid] != mid + 1):
      
        if (mid > 0 and 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 = [1, 2, 3, 3, 4, 5]
n = len(arr)
index = findRepeatingElement(arr, 0, n-1)
if (index is not -1):
    print arr[index]
  
#This code is contributed by Afzal Ansari

C#

// 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.

PHP

<?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)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter