Encuentra los dos elementos repetidos en una array dada

Se le da una array de n+2 elementos. Todos los elementos de la array están en el rango de 1 a n. Y todos los elementos ocurren una vez excepto dos números que ocurren dos veces. Encuentra los dos números que se repiten. 

Ejemplo:

Entrada: 
arr = [4, 2, 4, 5, 2, 3, 1] 
n = 5
Salida:
4 2
Explicación:
La array anterior tiene n + 2 = 7 elementos con todos los elementos que ocurren una vez excepto 2 y 4 que ocurren dos veces . Entonces la salida debería ser 4 2.

Método 1 (Básico) 

Usa dos bucles. En el ciclo externo, seleccione los elementos uno por uno y cuente el número de ocurrencias del elemento seleccionado en el ciclo interno. 
Este método no utiliza los otros datos útiles proporcionados en preguntas como el rango de números entre 1 y n y solo hay dos elementos repetidos.  

Complete Interview Preparation - GFG

C++

// C++ program to Find the two repeating
// elements in a given array
#include<bits/stdc++.h>
using namespace std;
  
void printTwoRepeatNumber(int arr[], int size)
{
    int i, j, display=0;
    int visited[size];
    for(i = 0; i < size; i++)
    {
    if (visited[i] == 1)
    {
        continue;
    }
    int count = 0;
        for(j = i + 1; j < size; j++)
        {
        if(arr[i] == arr[j])
        {
            visited[j] = 1;
            ++count;
            break;
        }
        }
        if ( (count > 0) && (display < 2)){
            ++display;
        cout<<"repeating element = "<< arr[i]<<endl;
        }
    }
}
  
int main()
{
    int arr[] = {4, 2, 5, 2, 3, 3, 4, 4, 1, 1};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printTwoRepeatNumber(arr, arr_size);
}

C

#include<stdio.h>
#include<stdlib.h>
void printRepeating(int arr[], int size)
{
  int i, j;
  printf(" Repeating elements are ");
  for(i = 0; i < size-1; i++)
    for(j = i+1; j < size; j++)
      if(arr[i] == arr[j])
        printf(" %d ", arr[i]);
}     
  
int main()
{
  int arr[] = {4, 2, 4, 5, 2, 3, 1};
  int arr_size = sizeof(arr)/sizeof(arr[0]);  
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Java

class RepeatElement 
{
    void printRepeating(int arr[], int size) 
    {
        int i, j;
        System.out.println("Repeated Elements are :");
        for (i = 0; i < size-1; i++) 
        {
            for (j = i + 1; j < size; j++) 
            {
                if (arr[i] == arr[j]) 
                    System.out.print(arr[i] + " ");
            }
        }
    }
  
    public static void main(String[] args) 
    {
        RepeatElement repeat = new RepeatElement();
        int arr[] = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}

Python3

# Python3 program to Find the two
# repeating elements in a given array
  
def printRepeating(arr, size):
  
    print("Repeating elements are ",
                         end = '')
    for i in range (0, size-1):
        for j in range (i + 1, size):
            if arr[i] == arr[j]:
                print(arr[i], end = ' ')
      
# Driver code
arr = [4, 2, 4, 5, 2, 3, 1]
arr_size = len(arr)
printRepeating(arr, arr_size)
  
# This code is contributed by Smitha Dinesh Semwal

C#

using System;
  
class GFG
{
          
    static void printRepeating(int []arr, int size) 
    {
        int i, j;
          
        Console.Write("Repeated Elements are :");
        for (i = 0; i < size-1; i++) 
        {
            for (j = i + 1; j < size; j++) 
            {
                if (arr[i] == arr[j]) 
                    Console.Write(arr[i] + " ");
            }
        }
    }
    // driver code
    public static void Main() 
    {
        int []arr = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.Length;
          
        printRepeating(arr, arr_size);
    }
}
  
// This code is contributed by Sam007

PHP

<?php
// PHP program to Find the two 
// repeating elements in 
// a given array
  
function printRepeating($arr, $size)
{
    $i;
    $j;
    echo " Repeating elements are ";
  
    for($i = 0; $i < $size-1; $i++)
        for($j = $i + 1; $j < $size; $j++)
            if($arr[$i] == $arr[$j])
                echo $arr[$i], " ";
} 
  
// Driver Code
$arr = array(4, 2, 4, 5, 2, 3, 1);
$arr_size = sizeof($arr, 0);
printRepeating($arr, $arr_size);
  
// This code is contributed by Ajit
?>

Javascript

<script>
    function printRepeating(arr , size) 
    {
        var i, j;
        document.write("Repeated Elements are :");
        for (i = 0; i < size-1; i++) 
        {
            for (j = i + 1; j < size; j++) 
            {
                if (arr[i] == arr[j]) 
                    document.write(arr[i] + " ");
            }
        }
    }
  
var arr = [4, 2, 4, 5, 2, 3, 1];
var arr_size = arr.length;
printRepeating(arr, arr_size);
  
// This code is contributed by 29AjayKumar
</script>
Producción

 Repeating elements are 4 2 

Complejidad temporal: O(n*n) 
Espacio auxiliar: O(1)

Método 2 (Usar array de conteo) 
Recorra la array una vez. Mientras se desplaza, realice un seguimiento del conteo de todos los elementos en la array utilizando un conteo de array temporal [] de tamaño n, cuando vea un elemento cuyo conteo ya está configurado, imprímalo como duplicado.
Este método usa el rango dado en la pregunta para restringir el tamaño de count[], pero no usa los datos de que solo hay dos elementos repetidos. 

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
  
void printRepeating(int arr[], int size) 
{ 
    int *count = new int[sizeof(int)*(size - 2)]; 
    int i; 
          
    cout << " Repeating elements are "; 
    for(i = 0; i < size; i++) 
    { 
        if(count[arr[i]] == 1) 
            cout << arr[i] << " "; 
        else
            count[arr[i]]++; 
    } 
} 
  
// Driver code
int main() 
{ 
    int arr[] = {4, 2, 4, 5, 2, 3, 1}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
    printRepeating(arr, arr_size); 
    return 0; 
} 
  
// This is code is contributed by rathbhupendra

C

#include<stdio.h>
#include<stdlib.h>
  
void printRepeating(int arr[], int size)
{
  int *count = (int *)calloc(sizeof(int), (size - 2));
  int i;
    
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
  {  
    if(count[arr[i]] == 1)
      printf(" %d ", arr[i]);
    else
     count[arr[i]]++;
  }    
}     
  
int main()
{
  int arr[] = {4, 2, 4, 5, 2, 3, 1};
  int arr_size = sizeof(arr)/sizeof(arr[0]);  
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Java

class RepeatElement
{
    void printRepeating(int arr[], int size) 
    {
        int count[] = new int[size];
        int i;
  
        System.out.println("Repeated elements are : ");
        for (i = 0; i < size; i++) 
        {
            if (count[arr[i]] == 1)
                System.out.print(arr[i] + " ");
            else
                count[arr[i]]++;
        }
    }
  
    public static void main(String[] args)
    {
        RepeatElement repeat = new RepeatElement();
        int arr[] = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}

Python3

# Python3 code for Find the two repeating 
# elements in a given array
  
  
def printRepeating(arr,size) :
    count = [0] * size
    print(" Repeating elements are ",end = "")
    for i in range(0, size) :
        if(count[arr[i]] == 1) :
            print(arr[i], end = " ")
        else :
            count[arr[i]] = count[arr[i]] + 1
  
  
# Driver code
arr = [4, 2, 4, 5, 2, 3, 1]
arr_size = len(arr)
printRepeating(arr, arr_size)
  
  
          
# This code is contributed by Nikita Tiwari.

C#

// C# program to Find the two
// repeating elements in a given array
using System;
  
class GFG
{
          
    static void printRepeating(int []arr,
                                    int size) 
    {
        int []count = new int[size];
        int i;
  
        Console.Write("Repeated elements are: ");
        for (i = 0; i < size; i++) 
        {
            if (count[arr[i]] == 1)
                Console.Write(arr[i] + " ");
            else
                count[arr[i]]++;
        }
    }
  
    // driver code
    public static void Main()
    {
        int []arr = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.Length;
          
        printRepeating(arr, arr_size);
    }
}
  
//This code is contributed by Sam007

PHP

<?php
// PHP program to Find the two
// repeating elements in a given array
function printRepeating($arr, $size) 
{ 
    $count = array_fill(0, $size, 0);
    echo "Repeated elements are ";
    for ($i = 0; $i < $size; $i++) 
    {
        if ($count[$arr[$i]] == 1)
            echo $arr[$i]." ";
        else
            $count[$arr[$i]]++;
    }
}
  
// Driver code
$arr = array(4, 2, 4, 5, 2, 3, 1);
$arr_size = count($arr);
  
printRepeating($arr, $arr_size);
          
// This code is contributed by mits
?>

Javascript

<script>
  
    // Javascript program to Find the two
    // repeating elements in a given array
        
    function printRepeating(arr, size)
    {
        let count = new Array(size);
        count.fill(0);
        let i;
   
        document.write("Repeating elements are ");
        for (i = 0; i < size; i++)
        {
            if (count[arr[i]] == 1)
                document.write(arr[i] + " ");
            else
                count[arr[i]]++;
        }
    }
      
    let arr = [4, 2, 4, 5, 2, 3, 1];
    let arr_size = arr.length;
  
    printRepeating(arr, arr_size);
      
</script>
Producción

 Repeating elements are 4 2 

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)

Método 3 (Hacer dos ecuaciones) 

Deje que los números que se repiten sean X e Y. Hacemos dos ecuaciones para X e Y y la tarea simple que queda es resolver las dos ecuaciones. 
Sabemos que la suma de los enteros del 1 al n es n(n+1)/2 y el producto es n!. Calculamos la suma de la array de entrada cuando esta suma se resta de n(n+1)/2, obtenemos X + Y porque X e Y son los dos números que faltan en el conjunto [1..n]. De manera similar, calcule el producto de la array de entrada, cuando este producto se divide de n!, obtenemos X*Y. Dada la suma y el producto de X e Y, podemos encontrar fácilmente X e Y.
Sea S la suma de todos los números en la array y el producto sea P
X + Y = S – n(n+1)/2 
XY = P /¡norte!
Usando las dos ecuaciones anteriores, podemos encontrar X e Y. Para array = 4 2 4 5 2 3 1, obtenemos S = 21 y P como 960.
X + Y = 21 – 15 = 6
XY = 960/5! = 8
X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2
Usando las siguientes dos ecuaciones, obtenemos fácilmente X = (6 + 2)/2 y Y = (6- 2)/2 
X + Y = 6 
X – Y = 2
Gracias a geek4u por sugerir este método. Como señaló Beginner, puede haber un problema de desbordamiento de sumas y multiplicaciones con este enfoque. 

Los métodos 3 y 4 utilizan toda la información útil proporcionada en la pregunta:

C++

#include <bits/stdc++.h>
using namespace std; 
  
/* function to get factorial of n */
int fact(int n); 
  
void printRepeating(int arr[], int size) 
{ 
    int S = 0; /* S is for sum of elements in arr[] */
    int P = 1; /* P is for product of elements in arr[] */
    int x, y; /* x and y are two repeating elements */
    int D; /* D is for difference of x and y, i.e., x-y*/
    int n = size - 2, i; 
      
    /* Calculate Sum and Product of all elements in arr[] */
    for(i = 0; i < size; i++) 
    { 
        S = S + arr[i]; 
        P = P*arr[i]; 
    }     
          
    S = S - n*(n+1)/2; /* S is x + y now */
    P = P/fact(n);     /* P is x*y now */
          
    D = sqrt(S*S - 4*P); /* D is x - y now */
          
    x = (D + S)/2; 
    y = (S - D)/2; 
          
    cout<<"The two Repeating elements are "<<x<<" & "<<y; 
} 
  
int fact(int n) 
{ 
    return (n == 0)? 1 : n*fact(n-1); 
} 
  
// Driver code
int main() 
{ 
    int arr[] = {4, 2, 4, 5, 2, 3, 1}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
    printRepeating(arr, arr_size); 
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
  
/* function to get factorial of n */
int fact(int n);
  
void printRepeating(int arr[], int size)
{
  int S = 0;  /* S is for sum of elements in arr[] */
  int P = 1;  /* P is for product of elements in arr[] */  
  int x,  y;   /* x and y are two repeating elements */
  int D;      /* D is for difference of x and y, i.e., x-y*/
  int n = size - 2,  i;
  
  /* Calculate Sum and Product of all elements in arr[] */
  for(i = 0; i < size; i++)
  {
    S = S + arr[i];
    P = P*arr[i];
  }        
    
  S = S - n*(n+1)/2;  /* S is x + y now */
  P = P/fact(n);         /* P is x*y now */
    
  D = sqrt(S*S - 4*P); /* D is x - y now */
    
  x = (D + S)/2;
  y = (S - D)/2;
    
  printf("The two Repeating elements are %d & %d", x, y);
}     
  
int fact(int n)
{
   return (n == 0)? 1 : n*fact(n-1);
}    
  
int main()
{
  int arr[] = {4, 2, 4, 5, 2, 3, 1};
  int arr_size = sizeof(arr)/sizeof(arr[0]);  
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Java

class RepeatElement
{
    void printRepeating(int arr[], int size) 
    {
        /* S is for sum of elements in arr[] */
        int S = 0;
          
        /* P is for product of elements in arr[] */
        int P = 1;
          
        /* x and y are two repeating elements */
        int x, y;
          
        /* D is for difference of x and y, i.e., x-y*/
        int D;
          
        int n = size - 2, i;
  
        /* Calculate Sum and Product of all elements in arr[] */
        for (i = 0; i < size; i++) 
        {
            S = S + arr[i];
            P = P * arr[i];
        }
  
        /* S is x + y now */
        S = S - n * (n + 1) / 2;
          
        /* P is x*y now */
        P = P / fact(n);
         
        /* D is x - y now */
        D = (int) Math.sqrt(S * S - 4 * P);
          
  
        x = (D + S) / 2;
        y = (S - D) / 2;
  
        System.out.println("The two repeating elements are :");
        System.out.print(x + " " + y);
    }
  
    int fact(int n) 
    {
        return (n == 0) ? 1 : n * fact(n - 1);
    }
  
    public static void main(String[] args) {
        RepeatElement repeat = new RepeatElement();
        int arr[] = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 code for Find the two repeating 
# elements in a given array
import math
  
def printRepeating(arr, size) :
      
    # S is for sum of elements in arr[] 
    S = 0; 
      
    # P is for product of elements in arr[] 
    P = 1;
      
    n = size - 2
  
    # Calculate Sum and Product 
    # of all elements in arr[] 
    for i in range(0, size) :
        S = S + arr[i]
        P = P * arr[i]
      
    # S is x + y now 
    S = S - n * (n + 1) // 2 
      
     # P is x*y now 
    P = P // fact(n)    
      
    # D is x - y now 
    D = math.sqrt(S * S - 4 * P) 
      
    x = (D + S) // 2
    y = (S - D) // 2
      
    print("The two Repeating elements are ", 
          (int)(x)," & " ,(int)(y))
      
  
def fact(n) :
    if(n == 0) :
        return 1
    else :
        return(n * fact(n - 1))
  
# Driver code
arr = [4, 2, 4, 5, 2, 3, 1]
arr_size = len(arr) 
printRepeating(arr, arr_size)
  
          
# This code is contributed by Nikita Tiwari.

C#

using System;
  
class GFG
{
          
    static void printRepeating(int []arr, int size) 
    {
        /* S is for sum of elements in arr[] */
        int S = 0;
          
        /* P is for product of elements in arr[] */
        int P = 1;
          
        /* x and y are two repeating elements */
        int x, y;
          
        /* D is for difference of x and y, i.e., x-y*/
        int D;
          
        int n = size - 2, i;
  
        /* Calculate Sum and Product 
         of all elements in arr[] */
        for (i = 0; i < size; i++) 
        {
            S = S + arr[i];
            P = P * arr[i];
        }
  
        /* S is x + y now */
        S = S - n * (n + 1) / 2;
          
        /* P is x*y now */
        P = P / fact(n);
          
        /* D is x - y now */
        D = (int) Math.Sqrt(S * S - 4 * P);
          
  
        x = (D + S) / 2;
        y = (S - D) / 2;
  
        Console.WriteLine("The two" + 
                " repeating elements are :");
        Console.Write(x + " " + y);
    }
  
    static int fact(int n) 
    {
        return (n == 0) ? 1 : n * fact(n - 1);
    }
  
    // driver code
    public static void Main() {
        int []arr = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.Length;
          
        printRepeating(arr, arr_size);
    }
}
// This code is contributed by Sam007 

PHP

<?php
  
/* function to get factorial of n */
function fact($n){
    
return ($n == 0)? 1 : $n*fact($n-1);
}
  
function printRepeating($arr, $size)
{
 $S = 0; /* S is for sum of elements in arr[] */
 $P = 1; /* P is for product of elements in arr[] */
 $x; $y; /* x and y are two repeating elements */
 $D;     /* D is for difference of x and y, i.e., x-y*/
 $n = $size - 2;
   
  
/* Calculate Sum and Product of all elements in arr[] */
for($i = 0; $i < $size; $i++)
{
    $S = $S + $arr[$i];
    $P = $P*$arr[$i];
}     
  
$S = $S - $n*($n+1)/2; /* S is x + y now */
$P = $P/fact($n);         /* P is x*y now */
  
$D = sqrt($S*$S - 4*$P); /* D is x - y now */
  
$x = ($D + $S)/2;
$y = ($S - $D)/2;
  
echo "The two Repeating elements are ".$x." & ".$y;
}     
  
  
  
$arr = array(4, 2, 4, 5, 2, 3, 1);
$arr_size = count($arr); 
printRepeating($arr, $arr_size);
?>

Javascript

<script>
  
    function printRepeating(arr , size) 
    {
        /* S is for sum of elements in arr */
        var S = 0;
          
        /* P is for product of elements in arr */
        var P = 1;
          
        /* x and y are two repeating elements */
        var x, y;
          
        /* D is for difference of x and y, i.e., x-y*/
        var D;
          
        var n = size - 2, i;
  
        /* Calculate Sum and Product of all elements in arr */
        for (i = 0; i < size; i++) 
        {
            S = S + arr[i];
            P = P * arr[i];
        }
  
        /* S is x + y now */
        S = S - n * parseInt((n + 1) / 2);
          
        /* P is x*y now */
        P = parseInt(P / fact(n));
         
        /* D is x - y now */
        D = parseInt( Math.sqrt(S * S - 4 * P));
          
  
        x = parseInt((D + S) / 2);
        y = parseInt((S - D) / 2);
  
        document.write("The two repeating elements are : ");
        document.write(x + " & " + y);
    }
  
    function fact(n) 
    {    var ans = false;
        if(n == 0)
            return 1;
        else
            return(n * fact(n - 1));
    }
  
      
    var arr = [4, 2, 4, 5, 2, 3, 1];
    var arr_size = arr.length;
    printRepeating(arr, arr_size);
  
// This code is contributed by 29AjayKumar 
  
</script>
Producción

The two Repeating elements are 4 & 2

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

 

Método 4 (Usar XOR) 

Gracias al neófito por sugerir este método. 
El enfoque utilizado aquí es similar al método 2 de esta publicación
Sean X e Y los números que se repiten, si hacemos x o todos los elementos de la array y todos los números enteros del 1 al n, entonces el resultado es X x o Y. 
Los 1 en la representación binaria de X x o Y corresponden a los diferentes bits entre X e Y. Supongamos que el k-ésimo bit de X x o Y es 1, podemos xor todos los elementos del arreglo y todos los enteros del 1 al n, cuyos k-ésimos bits sean 1. El resultado será uno de X e Y. 

C++

#include <bits/stdc++.h>
using namespace std;
  
void printRepeating(int arr[], int size) 
{ 
    int Xor = arr[0]; /* Will hold Xor of all elements */
    int set_bit_no; /* Will have only single set bit of Xor */
    int i; 
    int n = size - 2; 
    int x = 0, y = 0; 
          
    /* Get the Xor of all elements in arr[] and {1, 2 .. n} */
    for(i = 1; i < size; i++) 
        Xor ^= arr[i]; 
    for(i = 1; i <= n; i++) 
        Xor ^= i; 
      
    /* Get the rightmost set bit in set_bit_no */
    set_bit_no = Xor & ~(Xor-1); 
      
    /* Now divide elements in two sets by comparing rightmost set 
    bit of Xor with bit at same position in each element. */
    for(i = 0; i < size; i++) 
    { 
        if(arr[i] & set_bit_no) 
        x = x ^ arr[i]; /*Xor of first set in arr[] */
        else
        y = y ^ arr[i]; /*Xor of second set in arr[] */
    } 
    for(i = 1; i <= n; i++) 
    { 
        if(i & set_bit_no) 
        x = x ^ i; /*Xor of first set in arr[] and {1, 2, ...n }*/
        else
        y = y ^ i; /*Xor of second set in arr[] and {1, 2, ...n } */
    } 
          
    cout<<"The two repeating elements are "<<y<<" "<<x; 
} 
  
// Driver code
int main() 
{ 
    int arr[] = {4, 2, 4, 5, 2, 3, 1}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
    printRepeating(arr, arr_size); 
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

void printRepeating(int arr[], int size)
{
  int xor = arr[0]; /* Will hold xor of all elements */
  int set_bit_no;  /* Will have only single set bit of xor */
  int i;
  int n = size - 2;
  int x = 0, y = 0;
    
  /* Get the xor of all elements in arr[] and {1, 2 .. n} */
  for(i = 1; i < size; i++)
    xor ^= arr[i];  
  for(i = 1; i <= n; i++)
    xor ^= i;   
  
  /* Get the rightmost set bit in set_bit_no */
  set_bit_no = xor & ~(xor-1);
  
  /* Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. */
  for(i = 0; i < size; i++)
  {
    if(arr[i] & set_bit_no)
      x = x ^ arr[i]; /*XOR of first set in arr[] */
    else
      y = y ^ arr[i]; /*XOR of second set in arr[] */
  }
  for(i = 1; i <= n; i++)
  {
    if(i & set_bit_no)
      x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
    else
      y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
  }
    
  printf("n The two repeating elements are %d & %d ", x, y);
}     
  
  
int main()
{
  int arr[] = {4, 2, 4, 5, 2, 3, 1};
  int arr_size = sizeof(arr)/sizeof(arr[0]);  
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Java

class RepeatElement
{
    void printRepeating(int arr[], int size) 
    {
        /* Will hold xor of all elements */
        int xor = arr[0];
          
        /* Will have only single set bit of xor */
        int set_bit_no;
          
        int i;
        int n = size - 2;
        int x = 0, y = 0;
  
        /* Get the xor of all elements in arr[] and {1, 2 .. n} */
        for (i = 1; i < size; i++)
            xor ^= arr[i];
        for (i = 1; i <= n; i++)
            xor ^= i;
  
        /* Get the rightmost set bit in set_bit_no */
        set_bit_no = (xor & ~(xor - 1));
  
        /* Now divide elements in two sets by comparing rightmost set
           bit of xor with bit at same position in each element. */
        for (i = 0; i < size; i++) {
            int a = arr[i] & set_bit_no;
            if (a != 0)
                x = x ^ arr[i]; /*XOR of first set in arr[] */
            else
                y = y ^ arr[i]; /*XOR of second set in arr[] */
        }
        for (i = 1; i <= n; i++) 
        {
            int a = i & set_bit_no;
            if (a != 0)
                x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/
            else
                y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */
        }
  
        System.out.println("The two reppeated elements are :");
        System.out.println(x + " " + y);
    }
  
    /* Driver program to test the above function */
    public static void main(String[] args) 
    {
        RepeatElement repeat = new RepeatElement();
        int arr[] = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 code to Find the 
# two repeating elements 
# in a given array
def printRepeating(arr, size):
      
    # Will hold xor 
    # of all elements 
    xor = arr[0] 
    n = size - 2
    x = 0
    y = 0
      
    # Get the xor of all 
    # elements in arr[] 
    # and 1, 2 .. n 
    for i in range(1 , size):
        xor ^= arr[i] 
    for i in range(1 , n + 1):
        xor ^= i 
      
    # Get the rightmost set
    # bit in set_bit_no 
    set_bit_no = xor & ~(xor-1)
      
    # Now divide elements in two
    # sets by comparing rightmost 
    # set bit of xor with bit at
    # same position in each element. 
    for i in range(0, size):
          
        if(arr[i] & set_bit_no):
              
            # XOR of first 
            # set in arr[] 
            x = x ^ arr[i] 
        else:
              
            # XOR of second
            # set in arr[] 
            y = y ^ arr[i] 
              
    for i in range(1 , n + 1):
  
        if(i & set_bit_no):
              
            # XOR of first set
            # in arr[] and 
            # 1, 2, ...n 
            x = x ^ i 
        else:
              
             # XOR of second set 
             # in arr[] and
             # 1, 2, ...n 
            y = y ^ i
              
    print("The two repeating",
         "elements are", y, x)
  
# Driver code    
arr = [4, 2, 4, 
       5, 2, 3, 1]
arr_size = len(arr) 
printRepeating(arr, arr_size)
  
# This code is contributed 
# by Smitha

C#

using System;
  
class GFG
{
    static void printRepeating(int []arr, int size) 
    {
        /* Will hold xor of all elements */
        int xor = arr[0];
          
        /* Will have only single set bit of xor */
        int set_bit_no;
          
        int i;
        int n = size - 2;
        int x = 0, y = 0;
  
        /* Get the xor of all elements
         in arr[] and {1, 2 .. n} */
        for (i = 1; i < size; i++)
            xor ^= arr[i];
          
        for (i = 1; i <= n; i++)
            xor ^= i;
  
        /* Get the rightmost set bit in set_bit_no */
        set_bit_no = (xor & ~(xor - 1));
  
        /* Now divide elements in two sets by 
         comparing rightmost set bit of xor with bit
         at same position in each element. */
        for (i = 0; i < size; i++) {
            int a = arr[i] & set_bit_no;
          
            if (a != 0)
                /* XOR of first set in arr[] */
                x = x ^ arr[i]; 
            else
                /* XOR of second set in arr[] */
                y = y ^ arr[i]; 
        }
        for (i = 1; i <= n; i++) 
        {
            int a = i & set_bit_no;
              
            if (a != 0)
              
                /* XOR of first set in
                 arr[] and {1, 2, ...n }*/
                x = x ^ i; 
            else
              
                /* XOR of second set in 
                 arr[] and {1, 2, ...n } */
                y = y ^ i; 
        }
  
        Console.WriteLine("The two" + 
            " reppeated elements are :");
        Console.Write(x + " " + y);
    }
  
    /* Driver program to test the above function */
    public static void Main() 
    {
        int []arr = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.Length;
          
        printRepeating(arr, arr_size);
    }
}
  
// This code is contributed by Sam007

PHP

<?php 
// PHP code to Find the 
// two repeating elements 
// in a given array
function printRepeating( $arr, $size) 
{ 
    $xor = $arr[0]; /* Will hold xor of all elements */
    $set_bit_no; /* Will have only single set bit of xor */
    $i; 
    $n = $size - 2; 
    $x = 0; $y = 0; 
      
    /* Get the xor of all elements in arr[] and {1, 2 .. n} */
    for($i = 1; $i < $size; $i++) 
    $xor ^= $arr[$i]; 
    for($i = 1; $i <= $n; $i++) 
    $xor ^= $i; 
      
    /* Get the rightmost set bit in set_bit_no */
    $set_bit_no = $xor & ~($xor-1); 
      
    /* Now divide elements in two sets by 
    comparing rightmost set bit of xor with 
    bit at same position in each element. */
    for($i = 0; $i < $size; $i++) 
    { 
        if($arr[$i] & $set_bit_no) 
        $x = $x ^ $arr[$i]; /*XOR of first set in arr[] */
        else
        $y = $y ^ $arr[$i]; /*XOR of second set in arr[] */
          
    } 
    for($i = 1; $i <= $n; $i++) 
    { 
        if($i & $set_bit_no) 
        /*XOR of first set in arr[] and {1, 2, ...n }*/
        $x = $x ^ $i; 
        else
        /*XOR of second set in arr[] and {1, 2, ...n } */
        $y = $y ^ $i;
          
    } 
    echo "n The two repeating elements are ";
    echo $y. " ".$x;
      
} 
  
$arr = array(4, 2, 4, 5, 2, 3, 1); 
$arr_size = count($arr); 
printRepeating($arr, $arr_size); 
  
// This code has been contributed by Rajput-Ji
?>

Javascript

<script>
  
function printRepeating( arr, size) 
{ 
    let Xor = arr[0]; /* Will hold Xor of all elements */
    let set_bit_no; /* Will have only single set bit of Xor */
    let i; 
    let n = size - 2; 
    let x = 0, y = 0; 
          
    /* Get the Xor of all elements in arr[] and {1, 2 .. n} */
    for(i = 1; i < size; i++) 
        Xor ^= arr[i]; 
    for(i = 1; i <= n; i++) 
        Xor ^= i; 
      
    /* Get the rightmost set bit in set_bit_no */
    set_bit_no = Xor & ~(Xor-1); 
      
    /* Now divide elements in two sets by comparing rightmost set 
    bit of Xor with bit at same position in each element. */
    for(i = 0; i < size; i++) 
    { 
        if(arr[i] & set_bit_no) 
        x = x ^ arr[i]; /*Xor of first set in arr[] */
        else
        y = y ^ arr[i]; /*Xor of second set in arr[] */
    } 
    for(i = 1; i <= n; i++) 
    { 
        if(i & set_bit_no) 
        x = x ^ i; /*Xor of first set in arr[] and {1, 2, ...n }*/
        else
        y = y ^ i; /*Xor of second set in arr[] and {1, 2, ...n } */
    } 
          
    document.write("The two repeating elements are "+y+" "+x); 
} 
    // driver code 
    let arr = [4, 2, 4, 5, 2, 3, 1]; 
    let arr_size = arr.length; 
    printRepeating(arr, arr_size); 
      
    // This code is contributed by jana_sayantan.
</script>
Producción

The two repeating elements are 4 2

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

Método 5 (Usar elementos de array como índice) 
Gracias a Manish K. Aasawat por sugerir este método. 

Traverse the array. Do following for every index i of A[].
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
   this   element (ith element of list) is a repetition
}

Example: A[] =  {1, 1, 2, 3, 2}
i=0; 
Check sign of A[abs(A[0])] which is A[1].  A[1] is positive, so make it negative. 
Array now becomes {1, -1, 2, 3, 2}

i=1; 
Check sign of A[abs(A[1])] which is A[1].  A[1] is negative, so A[1] is a repetition.

i=2; 
Check sign of A[abs(A[2])] which is A[2].  A[2] is  positive, so make it negative. '
Array now becomes {1, -1, -2, 3, 2}

i=3; 
Check sign of A[abs(A[3])] which is A[3].  A[3] is  positive, so make it negative. 
Array now becomes {1, -1, -2, -3, 2}

i=4; 
Check sign of A[abs(A[4])] which is A[2].  A[2] is negative, so A[4] is a repetition.

Tenga en cuenta que este método modifica la array original y puede no ser un método recomendado si no se nos permite modificar la array. 

C++

#include <bits/stdc++.h>
using namespace std; 
  
void printRepeating(int arr[], int size) 
{ 
    int i; 
      
    cout << "The repeating elements are"; 
          
    for(i = 0; i < size; i++) 
    { 
        if(arr[abs(arr[i])] > 0) 
            arr[abs(arr[i])] = -arr[abs(arr[i])]; 
        else
            cout<<" " << abs(arr[i]) <<" "; 
    }     
} 
  
// Driver code
int main() 
{ 
    int arr[] = {4, 2, 4, 5, 2, 3, 1}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
    printRepeating(arr, arr_size); 
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

#include <stdio.h>
#include <stdlib.h>
  
void printRepeating(int arr[], int size)
{
  int i;  
   
  printf("\n The repeating elements are");
    
  for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }         
}     
  
int main()
{
  int arr[] = {4, 2, 4, 5, 2, 3, 1};
  int arr_size = sizeof(arr)/sizeof(arr[0]);
  printRepeating(arr, arr_size);
  getchar();
  return 0;
}

Java

class RepeatElement
{
    void printRepeating(int arr[], int size)
    {
        int i;  
        System.out.println("The repeating elements are : ");
     
        for(i = 0; i < size; i++)
        {
           int abs_val = Math.abs(arr[i]);
            if(arr[abs_val] > 0)
                arr[abs_val] = -arr[abs_val];
            else
                System.out.print(abs_val + " ");
        }         
    } 
  
    /* Driver program to test the above function */
    public static void main(String[] args) 
    {
        RepeatElement repeat = new RepeatElement();
        int arr[] = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python3 code for Find the two repeating 
# elements in a given array
  
  
def printRepeating(arr, size) :
      
    print(" The repeating elements are",end=" ")
      
    for i in range(0,size) :
          
        if(arr[abs(arr[i])] > 0) :
            arr[abs(arr[i])] = (-1) * arr[abs(arr[i])]
        else :
            print(abs(arr[i]),end = " ")
  
# Driver code
arr = [4, 2, 4, 5, 2, 3, 1]
arr_size = len(arr) 
printRepeating(arr, arr_size)
  
  
# This code is contributed by Nikita Tiwari.

C#

// C# code for Find the two repeating 
// elements in a given array
 using System;
  
class GFG
{
    static void printRepeating(int []arr, int size)
    {
        int i; 
        Console.Write("The repeating elements are : ");
      
        for(i = 0; i < size; i++)
        {
          int abs_val = Math.Abs(arr[i]);
            if(arr[abs_val] > 0)
                arr[abs_val] = -arr[abs_val];
            else
                Console.Write(abs_val + " ");
        }         
    } 
  
    /* Driver program to test the above function */
    public static void Main() 
    {
        int []arr = {4, 2, 4, 5, 2, 3, 1};
        int arr_size = arr.Length;
          
        printRepeating(arr, arr_size);
    }
}
  
// This code is contributed by Sam007

PHP

<?php
  
  
function  printRepeating($arr, $size)
{
    $i; 
  
 echo "The repeating elements are"," ";
  
for($i = 0; $i < $size; $i++)
{
    if($arr[abs($arr[$i])] > 0)
    $arr[abs($arr[$i])] = -$arr[abs($arr[$i])];
    else
    echo  abs($arr[$i])," ";
}         
}     
  
  
    $arr = array (4, 2, 4, 5, 2, 3, 1);
    $arr_size = sizeof($arr);
    printRepeating($arr, $arr_size);
      
      
#This code is contributed by aj_36
?>

Javascript

<script>
  
function printRepeating(arr , size)
{
    var i;  
    document.write("The repeating elements are : ");
     
        for(i = 0; i < size; i++)
        {
            var abs_val = Math.abs(arr[i]);
            if(arr[abs_val] > 0)x
                arr[abs_val] = -arr[abs_val];
            else
                document.write(abs_val + " ");
    }         
} 
  
/* Driver program to test the above function */
   
var arr = [4, 2, 4, 5, 2, 3, 1];
var arr_size = arr.length;
printRepeating(arr, arr_size);
  
// This code is contributed by 29AjayKumar 
  
</script>
Producción

The repeating elements are 4  2 

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

Método 6 (similar al método 5)

Gracias a Vivek Kumar por sugerir este método.

El punto es incrementar cada elemento en (arr[i]th-1)th index por N-1 (ya que los elementos están presentes solo hasta N-2) y al mismo tiempo verificar si el elemento en ese índice cuando se divide por ( N-1) da 2. Si esto es cierto, significa que el elemento ha aparecido dos veces y podemos decir fácilmente que esta es una de nuestras respuestas. Esta es una de las técnicas muy útiles cuando queremos calcular frecuencias de elementos de array de rango limitado  (consulte esta publicación para obtener más información).

Este método funciona con el hecho de que el resto de un elemento cuando se divide por cualquier número mayor que ese elemento siempre dará el mismo elemento. Del mismo modo, como estamos incrementando cada elemento en el índice (arr[i]th-1) por N-1, entonces cuando este elemento incrementado se divide por N-1 dará el número de veces que le hemos agregado N-1, por lo tanto, dándonos la ocurrencia de ese índice (según la indexación basada en 1).

A continuación, el código dado aplica este método:

C++

#include <iostream>
using namespace std;
  
void twoRepeated(int arr[], int N)
{
    int m = N - 1;
    for (int i = 0; i < N; i++) {
        arr[arr[i] % m - 1] += m;
        if ((arr[arr[i] % m - 1] / m) == 2)
            cout << arr[i] % m << " ";
    }
}
// Driver Code
int main()
{
    int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The two repeating elements are ";
    twoRepeated(arr, n);
  
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)

C

#include <stdio.h>
  
void twoRepeated(int arr[], int N)
{
    int m = N - 1;
    for (int i = 0; i < N; i++) {
        arr[arr[i] % m - 1] += m;
        if ((arr[arr[i] % m - 1] / m) == 2)
            printf("%d ", arr[i]);
    }
}
// Driver Code
int main()
{
    int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("The two repeating elements are ");
    twoRepeated(arr, n);
  
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)

Java

import java.io.*;
  
class GFG {
  
    public static void twoRepeated(int arr[], int N)
    {
        int m = N - 1;
        for (int i = 0; i < N; i++) {
            arr[arr[i] % m - 1] += m;
  
            if ((arr[arr[i] % m - 1] / m) == 2)
                System.out.printf(arr[i] % m + " ");
        }
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
        int n = 7;
        System.out.printf(
            "The two repeating elements are ");
        twoRepeated(arr, n);
    }
}
  
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python program for the above approach
def twoRepeated(arr, N):
    m = N - 1
    for i in range(N):
        arr[arr[i] % m - 1] += m
        if ((arr[arr[i] % m - 1] // m) == 2):
            print(arr[i] % m ,end= " ")
      
# Driver Code
arr = [4, 2, 4, 5, 2, 3, 1]
n = len(arr)
print("The two repeating elements are ", end = "")
twoRepeated(arr, n)
  
# This code is contributed by Shubham Singh

C#

// C# program for the above approach
using System;
  
public class GFG
{
public static void twoRepeated(int[] arr, int N)
{
    int m = N - 1;
    for(int i = 0; i < N; i++)
    {
        arr[arr[i] % m - 1] += m;
          
        if ((arr[arr[i] % m - 1] / m) == 2)
            Console.Write(arr[i] % m + " ");
    }
}
  
// Driver code
public static void Main(String []args)
{
    int[] arr = { 4, 2, 4, 5, 2, 3, 1 };
    int n = 7;
      
    Console.Write("The two repeating elements are ");
      
    twoRepeated(arr, n);
}
}
  
// This code is contributed by splevel62.

Javascript

<script>
  
function twoRepeated(arr, N) 
{
    let m = N - 1;
    for(let i = 0; i < N; i++) 
    {
        arr[parseInt(arr[i] % m) - 1] += m;
        if (parseInt(arr[parseInt(arr[i] % m) - 1] / m) == 2)
            document.write(parseInt(arr[i] % m) + " ");
    }
}
  
// Driver Code
var arr = [ 4, 2, 4, 5, 2, 3, 1 ];
var n = 7;
document.write("The two repeating elements are ");
  
twoRepeated(arr, n);
  
// This code is contributed by Potta Lokesh
  
</script>
Producción

The two repeating elements are 4 2 

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

Método 7
El punto aquí es ingresar los elementos del arreglo uno por uno en el conjunto desordenado. Si un elemento en particular ya está presente en el conjunto, es un elemento repetitivo.

C++

// C++ program to Find the two repeating 
// elements in a given array
#include <bits/stdc++.h>
using namespace std;
  
void printRepeating(int arr[], int size)
{
      unordered_set<int>s;
      cout<<"The two Repeating elements are : ";
    for(int i=0;i<size;i++)
    {
      if(s.empty()==false && s.find(arr[i])!=s.end())
        cout<<arr[i]<<"  ";
      s.insert(arr[i]);
    }
}
  
// Driver code
int main()
{
    int arr[] = {4, 2, 4, 5, 2, 3, 1};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printRepeating(arr, arr_size);
    return 0;
}
  
// This code is contributed by nakul amate

Java

// Java program to Find the two repeating 
// elements in a given array
import java.util.*;
class GFG{
  
  static void printRepeating(int arr[], int size)
  {
    HashSet<Integer>s = new HashSet<>();
    System.out.print("The two Repeating elements are : ");
    for(int i = 0; i < size; i++)
    {
      if(!s.isEmpty() && s.contains(arr[i]))
        System.out.print(arr[i]+"  ");
      s.add(arr[i]);
    }
  }
  
  // Driver code
  public static void main(String[] args)
  {
    int arr[] = {4, 2, 4, 5, 2, 3, 1};
    int arr_size = arr.length;
    printRepeating(arr, arr_size);
  }
}
  
// This code is contributed by Rajput-Ji

Python3

# Python3 program to find the two repeating 
# elements in a given array
def printRepeating(arr, size):
      
    s = set()
    print("The two Repeating elements are : ", end = "")
      
    for i in range(size):
        if (len(s) and arr[i] in s):
            print(arr[i], end = "  ")
              
        s.add(arr[i])
          
# Driver code
arr = [ 4, 2, 4, 5, 2, 3, 1 ]
arr_size = len(arr)
printRepeating(arr, arr_size)
  
# This code is contributed by Shubham Singh

C#

// C# program to Find the two repeating 
// elements in a given array
using System;
using System.Collections.Generic;
  
public class GFG{
      
  static void printRepeating(int[] arr, int size)
  {
    HashSet<int>s = new HashSet<int>();
    Console.Write("The two Repeating elements are : ");
    for(int i = 0; i < size; i++)
    {
      if(s.Count != 0 && s.Contains(arr[i]))
        Console.Write(arr[i] + "  ");
      s.Add(arr[i]);
    }
  }
  
  // Driver code
  public static void Main()
  {
    int[] arr = {4, 2, 4, 5, 2, 3, 1};
    int arr_size = arr.Length;
    printRepeating(arr, arr_size);
  }
}
  
// This code is contributed by Shubham Singh

Javascript

<script>
  
function printRepeating(arr, size) 
{
    const s = new Set();
    document.write("The two repeating elements are ");
    for(let i = 0; i < size; i++) 
    {
      if(s.size != 0 && s.has(arr[i]))
        document.write(arr[i] + " ");
      s.add(arr[i]);
              
    }
}
  
// Driver Code
var arr = [ 4, 2, 4, 5, 2, 3, 1 ];
var arr_size = 7;
printRepeating(arr, arr_size);
  
// This code is contributed by Shubham Singh
  
</script>
Producción

The two Repeating elements are : 4  2  

Complejidad de tiempo: O(n)  

Espacio Auxiliar: O(n)  

 
Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra mejores formas de resolver el mismo problema.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *