Encuentre duplicados en una array en O (n) y usando O (1) espacio adicional

Dada una array arr[] que contiene n + 1 enteros donde cada entero está entre 1 y n (inclusive). Solo hay un elemento duplicado, encuentre el elemento duplicado en la complejidad de tiempo O (n) y el espacio O (1).
Ejemplos: 
 

Input  : arr[] = {1, 4, 3, 4, 2} 
Output : 4

Input  : arr[] = {1, 3, 2, 1}
Output : 1

Enfoque: 
En primer lugar, las restricciones de este problema implican que debe existir un ciclo. Debido a que cada número en una array arr[] está entre 1 y n, necesariamente apuntará a un índice que existe. Por lo tanto, la lista se puede recorrer infinitamente, lo que implica que hay un ciclo. Además, debido a que 0 no puede aparecer como un valor en una array arr[], arr[0] no puede ser parte del ciclo. Por lo tanto, recorrer la array de esta manera desde arr[0] es equivalente a recorrer una lista enlazada cíclica. El problema se puede resolver como un ciclo de lista enlazada .
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP code to find the repeated elements
// in the array where every other is present once
#include <iostream>
using namespace std;
 
// Function to find duplicate
int findDuplicate(int arr[])
{
    // Find the intersection point of the slow and fast.
    int slow = arr[0];
    int fast = arr[0];
    do {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);
    // Find the "entrance" to the cycle.
    int ptr1 = arr[0];
    int ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = arr[ptr1];
        ptr2 = arr[ptr2];
    }
    return ptr1;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, 2, 1 };
    cout << findDuplicate(arr) << endl;
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

// C code to find the repeated elements
// in the array where every other is present once
#include <stdio.h>
 
// Function to find duplicate
int findDuplicate(int arr[])
{
    // Find the intersection point of the slow and fast.
    int slow = arr[0];
    int fast = arr[0];
    do {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);
 
    // Find the "entrance" to the cycle.
    int ptr1 = arr[0];
    int ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = arr[ptr1];
        ptr2 = arr[ptr2];
    }
    return ptr1;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 3, 2, 1 };
    printf("%d", findDuplicate(arr));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta (kriSania804)

// Java code to find the repeated
// elements in the array where
// every other is present once
import java.util.*;
 
class GFG
{
 
// Function to find duplicate
public static int findDuplicate(int []arr)
{
    // Find the intersection
    // point of the slow and fast.
    int slow = arr[0];
    int fast = arr[0];
    do
    {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);
 
    // Find the "entrance"
    // to the cycle.
    int ptr1 = arr[0];
    int ptr2 = slow;
    while (ptr1 != ptr2)
    {
        ptr1 = arr[ptr1];
        ptr2 = arr[ptr2];
    }
 
    return ptr1;
}
 
// Driver Code
public static void main(String[] args)
{
    int []arr = {1, 3, 2, 1};
 
    System.out.println("" +
               findDuplicate(arr));
 
    System.exit(0);
}
}
 
// This code is contributed
// by Harshit Saini

# Python code to find the
# repeated elements in the
# array where every other
# is present once
 
# Function to find duplicate
def findDuplicate(arr):
 
    # Find the intersection
    # point of the slow and fast.
    slow = arr[0]
    fast = arr[0]
    while True:
        slow = arr[slow]
        fast = arr[arr[fast]]
        if slow == fast:
            break
 
    # Find the "entrance"
    # to the cycle.
    ptr1 = arr[0]
    ptr2 = slow
    while ptr1 != ptr2:
        ptr1 = arr[ptr1]
        ptr2 = arr[ptr2]
         
    return ptr1
     
# Driver code
if __name__ == '__main__':
     
     
    arr = [ 1, 3, 2, 1 ]
 
    print(findDuplicate(arr))
 
 
# This code is contributed
# by Harshit Saini

// C# code to find the repeated
// elements in the array where
// every other is present once
using System;
 
class GFG
{
 
// Function to find duplicate
public static int findDuplicate(int []arr)
{
    // Find the intersection
    // point of the slow and fast.
    int slow = arr[0];
    int fast = arr[0];
    do
    {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);
 
    // Find the "entrance"
    // to the cycle.
    int ptr1 = arr[0];
    int ptr2 = slow;
    while (ptr1 != ptr2)
    {
        ptr1 = arr[ptr1];
        ptr2 = arr[ptr2];
    }
 
    return ptr1;
}
 
// Driver Code
public static void Main()
{
    int[] arr = {1, 3, 2, 1};
 
    Console.WriteLine("" +
            findDuplicate(arr));
 
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

<?php
// PHP code to find the repeated
// elements in the array where
// every other is present once
 
// Function to find duplicate
function findDuplicate(&$arr)
{
    $slow = $arr[0];
    $fast = $arr[0];
    do
    {
        $slow = $arr[$slow];
        $fast = $arr[$arr[$fast]];
    } while ($slow != $fast);
 
    // Find the "entrance"
    // to the cycle.
    $ptr1 = $arr[0];
    $ptr2 = $slow;
    while ($ptr1 != $ptr2)
    {
        $ptr1 = $arr[$ptr1];
        $ptr2 = $arr[$ptr2];
    }
 
    return $ptr1;
}
 
// Driver code
$arr = array(1, 3, 2, 1);
echo " " . findDuplicate($arr);
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
// JavaScript code to find the repeated elements
// in the array where every other is present once
 
// Function to find duplicate
function findDuplicate(arr)
{
 
    // Find the intersection point of
    // the slow and fast.
    let slow = arr[0];
    let fast = arr[0];
    do
    {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);
 
    // Find the "entrance" to the cycle.
    let ptr1 = arr[0];
    let ptr2 = slow;
    while (ptr1 != ptr2)
    {
        ptr1 = arr[ptr1];
        ptr2 = arr[ptr2];
    }
    return ptr1;
}
 
// Driver code
    let arr = [ 1, 3, 2, 1 ];
    document.write(findDuplicate(arr) + "<br>");
     
// This code is contributed by Surbhi Tyagi.
</script>

1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)