Nos dan una array arr[] de tamaño n. Los números van del 1 al (n-1) en orden aleatorio. La array tiene un solo elemento repetitivo. Necesitamos encontrar el elemento repetitivo.
Ejemplos:
Input : a[] = {1, 3, 2, 3, 4}
Output : 3
Input : a[] = {1, 5, 1, 2, 3, 4}
Output : 1
Método 1 (Simple) Usamos dos bucles anidados. El bucle exterior atraviesa todos los elementos y el bucle interior comprueba si el elemento seleccionado por el bucle exterior aparece en algún otro lugar.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int n)
{
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] == arr[j])
return arr[i];
}
}
}
// Driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, n);
return 0;
}
// This code is added by Arpit Jain
Java
// Java program to find the only repeating
// element in an array where elements are
// from 1 to n-1.using System;
public class GFG {
static int findRepeating(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j])
return arr[i];
}
}
return -1;
}
// Driver code
static public void main(String[] args)
{
// Code
int[] arr
= new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int repeatingNum = findRepeating(arr);
System.out.println(repeatingNum);
}
}
// This code is contributed by phasing17
Python3
# Python3 program to find the only # repeating element in an array where # elements are from 1 to n-1. def findRepeating(arr, n): for i in range(n): for j in range(i + 1, n): if (arr[i] == arr[j]): return arr[i]; # Driver Code arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7] n = len(arr) print(findRepeating(arr, n)) # This code is contributed by Arpit Jain
C#
// C# program to find the only repeating
// element in an array where elements are
// from 1 to n-1.using System;
public class GFG {
static int findRepeating(int[] arr)
{
for (int i = 0; i < arr.Length; i++) {
for (int j = i + 1; j < arr.Length; j++) {
if (arr[i] == arr[j])
return arr[i];
}
}
return -1;
}
// Driver code
static public void Main()
{
// Code
int[] arr = new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int repeatingNum = findRepeating(arr);
Console.WriteLine(repeatingNum);
}
}
// This code is contributed by Mohd Nizam
Producción
8
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Método 2 (usando clasificación) ,
- primero ordene la array y simplemente compare el elemento de la array con su índice
- si arr[i] != i+1, significa que arr[i] es repetitivo.
- Así que solo regresa arr[I]
- De lo contrario, la array no contiene duplicados de 1 a n-1
- En este caso devuelve -1
C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int n)
{
sort(arr, arr + n); // sort array
for (int i = 0; i <= n; i++) {
// compare array element with its index
if (arr[i] != i + 1) {
return arr[i];
}
}
return -1;
}
// driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, n);
return 0;
}
// this code is contributed by devendra solunke
Java
// Java program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
import java.util.Arrays;
public class GFG {
static int findRepeating(int[] arr,int n)
{
Arrays.sort(arr); // sort array
for (int i = 0; i <= n; i++) {
// compare array element with its index
if (arr[i] != i + 1) {
return arr[i];
}
}
return -1;
}
// Driver code
static public void main(String[] args)
{
// Code
int[] arr = new int[] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.length;
int repeatingNum = findRepeating(arr,n);
System.out.println(repeatingNum);
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to find the only repeating element in an array
// where elements are from 1 to n-1.
using System;
public class GFG {
static int findRepeating(int[] arr, int n)
{
Array.Sort(arr); // sort array
for (int i = 0; i <= n; i++) {
// compare array element with its index
if (arr[i] != i + 1) {
return arr[i];
}
}
return -1;
}
static public void Main()
{
// Code
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.Length;
int repeatingNum = findRepeating(arr, n);
Console.WriteLine(repeatingNum);
}
}
// This code is contributed by lokesh (lokeshmvs21).
Producción
8
Complejidad de tiempo: O(N*log N) compara cada elemento de la array con su índice
Espacio auxiliar: O(1)
Método 3 (usando la fórmula de la suma): Sabemos que la suma de los primeros n-1 números naturales es (n – 1)*n/2. Calculamos la suma de los elementos de la array y le restamos la suma de los números naturales para encontrar el único elemento que falta.
C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int n)
{
// Find array sum and subtract sum
// first n-1 natural numbers from it
// to find the result.
return accumulate(arr , arr+n , 0) -
((n - 1) * n/2);
}
// driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Java
// Java program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
import java.io.*;
import java.util.*;
class GFG
{
static int findRepeating(int[] arr, int n)
{
// Find array sum and subtract sum
// first n-1 natural numbers from it
// to find the result.
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum - (((n - 1) * n) / 2);
}
// Driver code
public static void main(String args[])
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.length;
System.out.println(findRepeating(arr, n));
}
}
// This code is contributed by rachana soma
Python3
# Python3 program to find the only # repeating element in an array where # elements are from 1 to n-1. def findRepeating(arr, n): # Find array sum and subtract sum # first n-1 natural numbers from it # to find the result. return sum(arr) -(((n - 1) * n) // 2) # Driver Code arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7] n = len(arr) print(findRepeating(arr, n)) # This code is contributed # by mohit kumar
C#
// C# program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
using System;
class GFG
{
static int findRepeating(int[] arr, int n)
{
// Find array sum and subtract sum
// first n-1 natural numbers from it
// to find the result.
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum - (((n - 1) * n) / 2);
}
// Driver code
public static void Main(String []args)
{
int[] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.Length;
Console.WriteLine(findRepeating(arr, n));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// javascript program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
function findRepeating(arr , n)
{
// Find array sum and subtract sum
// first n-1 natural numbers from it
// to find the result.
var sum = 0;
for (i = 0; i < n; i++)
sum += arr[i];
return sum - (((n - 1) * n) / 2);
}
// Driver code
var arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
var n = arr.length;
document.write(findRepeating(arr, n));
// This code is contributed by Rajput-Ji
</script>
Producción
8
Complejidad de tiempo: O(n)
Espacio auxiliar: O(1)
Provoca desbordamiento para arreglos grandes.
Método 4 (Usar Hashing): Use una tabla hash para almacenar los elementos visitados. Si vuelve a aparecer un elemento visto, lo devolvemos.
C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int n)
{
unordered_set<int> s;
for (int i=0; i<n; i++)
{
if (s.find(arr[i]) != s.end())
return arr[i];
s.insert(arr[i]);
}
// If input is correct, we should
// never reach here
return -1;
}
// driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Java
import java.util.*;
// Java program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
class GFG
{
static int findRepeating(int arr[], int n)
{
HashSet<Integer> s = new HashSet<Integer>();
for (int i = 0; i < n; i++)
{
if (s.contains(arr[i]))
return arr[i];
s.add(arr[i]);
}
// If input is correct, we should
// never reach here
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.length;
System.out.println(findRepeating(arr, n));;
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the only # repeating element in an array # where elements are from 1 to n-1. def findRepeating(arr, n): s = set() for i in range(n): if arr[i] in s: return arr[i] s.add(arr[i]) # If input is correct, we should # never reach here return -1 # Driver code arr = [9, 8, 2, 6, 1, 8, 5, 3] n = len(arr) print(findRepeating(arr, n)) # This code is contributed # by Shrikant13
C#
// C# program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
using System;
using System.Collections.Generic;
class GFG
{
static int findRepeating(int []arr, int n)
{
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++)
{
if (s.Contains(arr[i]))
return arr[i];
s.Add(arr[i]);
}
// If input is correct, we should
// never reach here
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.Length;
Console.WriteLine(findRepeating(arr, n));;
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
function findRepeating(arr,n)
{
s = new Set();
for (let i = 0; i < n; i++)
{
if (s.has(arr[i]))
return arr[i];
s.add(arr[i]);
}
// If input is correct, we should
// never reach here
return -1;
}
// driver code
let arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let n = arr.length;
document.write(findRepeating(arr, n));
// This code is contributed by shinjanpatra.
</script>
Producción
8
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método 5 (Usar XOR): La idea se basa en el hecho de que x ^ x = 0 y x ^ y = y ^ x.
1) Calcular XOR de elementos de 1 a n-1.
2) Calcular XOR de elementos de array.
3) XOR de los dos anteriores sería nuestro resultado.
C++
// CPP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
int findRepeating(int arr[], int n)
{
// res is going to store value of
// 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^
// arr[1] ^ .... arr[n-1]
int res = 0;
for (int i=0; i<n-1; i++)
res = res ^ (i+1) ^ arr[i];
res = res ^ arr[n-1];
return res;
}
// driver code
int main()
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Java
// Java program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
class GFG
{
static int findRepeating(int arr[], int n)
{
// res is going to store value of
// 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^
// arr[1] ^ .... arr[n-1]
int res = 0;
for (int i = 0; i < n - 1; i++)
res = res ^ (i + 1) ^ arr[i];
res = res ^ arr[n - 1];
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.length;
System.out.println(findRepeating(arr, n));
}
}
// This code is contributed by
// Smitha Dinesh Semwal.
Python3
# Python3 program to find the only # repeating element in an array where # elements are from 1 to n-1. def findRepeating(arr, n): # res is going to store value of # 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^ # arr[1] ^ .... arr[n-1] res = 0 for i in range(0, n-1): res = res ^ (i+1) ^ arr[i] res = res ^ arr[n-1] return res # Driver code arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7] n = len(arr) print(findRepeating(arr, n)) # This code is contributed by Smitha Dinesh Semwal.
C#
// C# program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
using System;
public class GFG
{
static int findRepeating(int []arr, int n)
{
// res is going to store value of
// 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^
// arr[1] ^ .... arr[n-1]
int res = 0;
for (int i = 0; i < n - 1; i++)
res = res ^ (i + 1) ^ arr[i];
res = res ^ arr[n - 1];
return res;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 };
int n = arr.Length;
Console.WriteLine(findRepeating(arr, n));
}
}
// This code is contributed by Rajput-Ji
PHP
<?php
// PHP program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
function findRepeating($arr, $n)
{
// res is going to store value of
// 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^
// arr[1] ^ .... arr[n-1]
$res = 0;
for($i = 0; $i < $n - 1; $i++)
$res = $res ^ ($i + 1) ^ $arr[$i];
$res = $res ^ $arr[$n - 1];
return $res;
}
// Driver Code
$arr =array(9, 8, 2, 6, 1, 8, 5, 3, 4, 7);
$n = sizeof($arr) ;
echo findRepeating($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to find the only repeating
// element in an array where elements are
// from 1 to n-1.
function findRepeating(arr,n)
{
// res is going to store value of
// 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^
// arr[1] ^ .... arr[n-1]
let res = 0;
for (let i=0; i<n-1; i++)
res = res ^ (i+1) ^ arr[i];
res = res ^ arr[n-1];
return res;
}
// driver code
let arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];
let n = arr.length;
document.write(findRepeating(arr, n));
</script>
Producción
8
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Método 6: Usando la indexación.
1. Iterar a través de la array.
2. Para cada índice, visite un [índice], si es positivo, cambie el signo del elemento en un índice [índice], de lo contrario, imprima el elemento.
C++
// CPP program to find the only
// repeating element in an array
// where elements are from 1 to n-1.
#include <bits/stdc++.h>
using namespace std;
// Function to find repeated element
int findRepeating(int arr[], int n)
{
int missingElement = 0;
// indexing based
for (int i = 0; i < n; i++){
int element = arr[abs(arr[i])];
if(element < 0){
missingElement = arr[i];
break;
}
arr[abs(arr[i])] = -arr[abs(arr[i])];
}
return abs(missingElement);
}
// driver code
int main()
{
int arr[] = { 5, 4, 3, 9, 8,
9, 1, 6, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findRepeating(arr, n);
return 0;
}
Java
// Java program to find the only
// repeating element in an array
// where elements are from 1 to n-1.
import java.lang.Math.*;
class GFG
{
// Function to find repeated element
static int findRepeating(int arr[], int n)
{
int missingElement = 0;
// indexing based
for (int i = 0; i < n; i++){
int absVal = Math.abs(arr[i]);
int element = arr[absVal];
if(element < 0){
missingElement = arr[i];
break;
}
int absVal = Math.abs(arr[i]);
arr[absVal] = -arr[absVal];
}
return Math.abs(missingElement);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 4, 3, 9, 8,
9, 1, 6, 2, 5};
int n = arr.length;
System.out.println(findRepeating(arr, n));
}
}
// This code is contributed by
// Smitha Dinesh Semwal.
Python3
# Python3 program to find the only # repeating element in an array # where elements are from 1 to n-1. # Function to find repeated element def findRepeating(arr, n): missingElement = 0 # indexing based for i in range(0, n): element = arr[abs(arr[i])] if(element < 0): missingElement = arr[i] break arr[abs(arr[i])] = -arr[abs(arr[i])] return abs(missingElement) # Driver code arr = [5, 4, 3, 9, 8, 9, 1, 6, 2, 5] n = len(arr) print(findRepeating(arr, n)) # This code is contributed by Smitha Dinesh Semwal.
C#
// C# program to find the only
// repeating element in an array
// where elements are from 1 to n-1.
using System;
public class GFG
{
// Function to find repeated element
static int findRepeating(int[] arr, int n)
{
int missingElement = 0;
// indexing based
for (int i = 0; i < n; i++) {
int absVal = Math.abs(arr[i]);
int element = arr[absVal];
if (element < 0) {
missingElement = arr[i];
break;
}
int absVal = Math.abs(arr[i]);
arr[absVal] = -arr[absVal];
}
return Math.Abs(missingElement);
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 5, 4, 3, 9, 8, 9, 1, 6, 2, 5 };
int n = arr.Length;
Console.WriteLine(findRepeating(arr, n));
}
}
// this code is contributed by phasing17
PHP
<?php
// PHP program to find the only
// repeating element in an array
// where elements are from 1 to n-1.
// Function to find repeated elements
function findRepeating($arr, $n)
{
$missingElement = 0;
// indexing based
for ($i = 0; $i < $n; $i++)
{
$element = $arr[abs($arr[$i])];
if($element < 0)
{
$missingElement = $arr[$i];
break;
}
$arr[abs($arr[$i])] = -$arr[abs($arr[$i])];
}
return abs($missingElement);
}
// Driver Code
$arr = array (5, 4, 3, 9, 8,
9, 1, 6, 2, 5);
$n = sizeof($arr);
echo findRepeating($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program for the above approach;
// Function to find repeated element
function findRepeating(arr, n) {
let missingElement = 0;
// indexing based
for (let i = 0; i < n; i++) {
let absVal = Math.abs(arr[i]);
let element = arr[absVal];
if (element < 0) {
missingElement = arr[i];
break;
}
let absVal = Math.abs(arr[i]);
arr[absVal] = -arr[absVal];
}
return Math.abs(missingElement);
}
// driver code
let arr = [5, 4, 3, 9, 8,
9, 1, 6, 2, 5];
let n = arr.length;
document.write(findRepeating(arr, n));
// This code is contributed by Potta Lokesh
</script>
Producción
9
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Método 7: (Método de ciclo de lista enlazada)
Usa dos punteros, el rápido y el lento. El rápido avanza dos pasos cada vez, mientras que el lento solo avanza un paso cada vez. Deben encontrarse con el mismo elemento cuando lento==rápido. De hecho, se encuentran en un círculo, el número duplicado debe ser el punto de entrada del círculo cuando se visita la array desde array[0]. A continuación, solo tenemos que encontrar el punto de entrada. Usamos un punto (podemos usar el rápido antes) para visitar el formulario comenzando con un paso cada vez, hacemos el mismo trabajo para reducir la velocidad. Cuando rápido == lento, se encuentran en el punto de entrada del círculo. El código de fácil comprensión es el siguiente.
C++
#include <bits/stdc++.h>
using namespace std;
int findDuplicate(vector<int>& nums)
{
int slow = nums[0];
int fast = nums[0];
do{
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow!=fast);
fast = nums[0];
while(slow!=fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
int main()
{
vector<int> v{ 1, 3, 2, 3, 4 };
int ans = findDuplicate(v);
cout << ans << endl;
return 0;
}
Producción
3
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shashank_Pathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA