Encuentre cualquiera de los múltiples elementos repetidos en una array de solo lectura | conjunto 2

Dada una array de solo lectura arr[] de tamaño N + 1 , encuentre uno de los múltiples elementos repetidos en la array donde la array contiene números enteros solo entre 1 y N . 
Nota: la array de solo lectura significa que el contenido de la array no se puede modificar.

Ejemplos: 

Entrada: N = 5, arr[] = {1, 1, 2, 3, 5, 4} 
Salida: 1 
Explicación: 
1 es el único número repetido en la array.

Entrada: N = 10, arr[] = {10, 1, 2, 3, 5, 4, 9, 8, 5, 6, 4} 
Salida: 5 
Explicación: 
5 es el del número repetido en el arreglo. 
 

En la publicación anterior , hemos discutido el mismo artículo con una complejidad espacial O(N) y O(sqrt(N)) .

Enfoque: Este enfoque se basa en el Algoritmo de Tortuga y Liebre de Floyd ( Algoritmo de Detección de Ciclo ). 

• Usa la función f(x) = arr[x] para construir la secuencia:

arr[0], arr[arr[0]], arr[arr[arr[0]]], arr[arr[arr[arr[0]]]] ……. 
 

• Cada nuevo elemento en la secuencia es un elemento en arr[] en el índice del elemento anterior.
• A partir de x = arr[0] , producirá una lista enlazada con un ciclo.
• El ciclo aparece porque arr[] contiene elementos duplicados (al menos uno). El valor duplicado es una entrada al ciclo. A continuación se muestra un ejemplo para mostrar cómo existe el ciclo: 
  Por ejemplo: Deje que la array arr[] = {2, 6, 4, 1, 3, 1, 5} 
   

A partir del índice 0, el recorrido se ve de la siguiente manera: 

array[0] = 2 –> array[2] = 4 –> array[4] = 3 –> array[3] = 1 –> array[1] = 6 –> array[6] = 5 –> array[ 5] = 1 . 
 

La secuencia forma un ciclo como se muestra a continuación: 
 

• El algoritmo consta de dos partes y utiliza dos punteros, generalmente llamados Turtle y liebre .
•  liebre = arr[arr[liebre]] es el doble de rápido que Turtle = arr[Turtle] .
• Como la liebre va rápido, sería la primera que entra en el ciclo y comienza a correr alrededor del ciclo.
• En algún momento, la Turtle también entra en el ciclo, y dado que se mueve más lento, la liebre atrapa a la Turtle en algún punto de intersección.
• Tenga en cuenta que el punto de intersección no es la entrada del ciclo en el caso general, sino que los dos se cruzan en algún punto medio del ciclo.
• Mueve la Turtle al punto de inicio de la secuencia y la liebre permanece dentro del ciclo y ambas se mueven con la misma velocidad, es decir, Turtle = arr[Turtle] y liebre = arr[liebre] . Ahora se cruzan en el elemento duplicado.

A continuación se muestra la implementación del enfoque anterior:

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the duplicate
// value in the given array arr[]
void findDuplicate(int arr[])
{
 
    // Initialise variables
    int tortoise = arr[0];
    int hare = arr[0];
 
    // Loop till we find the
    // duplicate element
    while (1) {
 
        tortoise = arr[tortoise];
 
        // Hare moves with twice
        // the speed of tortoise
        hare = arr[arr[hare]];
        if (tortoise == hare)
            break;
    }
 
    tortoise = arr[0];
 
    // Loop to get start point
    // of the cycle as start
    // point will be the duplicate
    // element
    while (tortoise != hare) {
        tortoise = arr[tortoise];
        hare = arr[hare];
    }
 
    // Print the duplicate element
    cout << tortoise;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 6, 4, 1, 3, 1, 5 };
 
    // Function Call
    findDuplicate(arr);
 
    return 0;
}

// Java code for the above approach
class GFG{
 
// Function to find the duplicate
// value in the given array arr[]
static void findDuplicate(int arr[])
{
     
    // Initialise variables
    int tortoise = arr[0];
    int hare = arr[0];
 
    // Loop till we find the
    // duplicate element
    while (true)
    {
        tortoise = arr[tortoise];
         
        // Hare moves with twice
        // the speed of tortoise
        hare = arr[arr[hare]];
        if (tortoise == hare)
            break;
    }
     
    tortoise = arr[0];
 
    // Loop to get start point
    // of the cycle as start
    // point will be the duplicate
    // element
    while (tortoise != hare)
    {
        tortoise = arr[tortoise];
        hare = arr[hare];
    }
 
    // Print the duplicate element
    System.out.print(tortoise);
}
 
// Driver Code
public static void main (String []args)
{
     
    // Given array
    int arr[] = { 2, 6, 4, 1, 3, 1, 5 };
 
    // Function Call
    findDuplicate(arr);
}
}
 
// This code is contributed by chitranayal

# Python3 program for the above approach
 
# Function to find the duplicate
# value in the given array arr[]
def findDuplicate(arr):
 
    # Initialise variables
    tortoise = arr[0]
    hare = arr[0]
 
    # Loop till we find the
    # duplicate element
    while (1):
 
        tortoise = arr[tortoise]
 
        # Hare moves with twice
        # the speed of tortoise
        hare = arr[arr[hare]]
        if (tortoise == hare):
            break
 
    tortoise = arr[0]
 
    # Loop to get start point
    # of the cycle as start
    # point will be the duplicate
    # element
    while (tortoise != hare):
        tortoise = arr[tortoise]
        hare = arr[hare]
 
    # Print the duplicate element
    print (tortoise)
 
# Driver Code
 
# Given array
arr = [ 2, 6, 4, 1, 3, 1, 5 ]
 
# Function Call
findDuplicate(arr)
 
# This code is contributed by PratikBasu

// C# program for the above approach
using System;
 
class GFG{
  
// Function to find the duplicate
// value in the given array []arr
static void findDuplicate(int []arr)
{
      
    // Initialise variables
    int tortoise = arr[0];
    int hare = arr[0];
  
    // Loop till we find the
    // duplicate element
    while (true)
    {
        tortoise = arr[tortoise];
          
        // Hare moves with twice
        // the speed of tortoise
        hare = arr[arr[hare]];
        if (tortoise == hare)
            break;
    }
      
    tortoise = arr[0];
  
    // Loop to get start point
    // of the cycle as start
    // point will be the duplicate
    // element
    while (tortoise != hare)
    {
        tortoise = arr[tortoise];
        hare = arr[hare];
    }
  
    // Print the duplicate element
    Console.Write(tortoise);
}
  
// Driver Code
public static void Main(String []args)
{
      
    // Given array
    int []arr = { 2, 6, 4, 1, 3, 1, 5 };
  
    // Function Call
    findDuplicate(arr);
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript code for the above approach
 
// Function to find the duplicate
// value in the given array arr[]
function findDuplicate(arr)
{
     
    // Initialise variables
    let tortoise = arr[0];
    let hare = arr[0];
 
    // Loop till we find the
    // duplicate element
    while (true)
    {
        tortoise = arr[tortoise];
         
        // Hare moves with twice
        // the speed of tortoise
        hare = arr[arr[hare]];
         
        if (tortoise == hare)
            break;
    }
     
    tortoise = arr[0];
 
    // Loop to get start point
    // of the cycle as start
    // point will be the duplicate
    // element
    while (tortoise != hare)
    {
        tortoise = arr[tortoise];
        hare = arr[hare];
    }
     
    // Print the duplicate element
    document.write(tortoise);
}
     
// Driver Code
 
// Given array
let arr = [ 2, 6, 4, 1, 3, 1, 5 ];
 
// Function Call
findDuplicate(arr);
 
// This code is contributed by sanjoy_62  
 
</script>

1

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