Dada una array desordenada de tamaño n. Los elementos de la array están en el rango de 1 a n. Falta un número del conjunto {1, 2, … n} y un número aparece dos veces en la array. Encuentra estos dos números.
Ejemplos:
Entrada: arr[] = {3, 1, 3}
Salida: Falta = 2, Repetición = 3
Explicación: En la array, falta 2 y 3 aparece dos vecesEntrada: arr[] = {4, 3, 6, 2, 1, 1}
Salida: Falta = 5, Repetición = 1
A continuación se presentan varios métodos para resolver los problemas:
Método 1 (Clasificación de uso)
Enfoque:
- Ordenar la array de entrada.
- Atraviese la array y verifique si faltan y se repiten.
Complejidad de tiempo: O (nLogn)
Gracias a LoneShadow por sugerir este método.
Método 2 (Usar array de conteo)
Enfoque:
- Cree una array temporal temp[] de tamaño n con todos los valores iniciales como 0.
- Recorra la array de entrada arr[] y haga lo siguiente para cada arr[i]
- if(temp[arr[i]] == 0) temp[arr[i]] = 1;
- if(temp[arr[i]] == 1) salida “arr[i]” //repetir
- Traverse temp[] y generar el elemento de la array que tiene un valor de 0 (este es el elemento que falta)
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método 3 (Usar elementos como índice y marcar los lugares visitados)
Enfoque:
recorrer la array. Mientras atraviesa, use el valor absoluto de cada elemento como índice y haga que el valor en este índice sea negativo para marcarlo como visitado. Si algo ya está marcado como negativo, entonces este es el elemento repetido. Para encontrar lo que falta, recorra la array nuevamente y busque un valor positivo.
C++
// C++ program to Find the repeating
// and missing elements
#include <bits/stdc++.h>
using namespace std;
void printTwoElements(int arr[], int size)
{
int i;
cout << "The repeating element is ";
for (i = 0; i < size; i++) {
if (arr[abs(arr[i]) - 1] > 0)
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
else
cout << abs(arr[i]) << "\n";
}
cout << "and the missing element is ";
for (i = 0; i < size; i++) {
if (arr[i] > 0)
cout << (i + 1);
}
}
/* Driver code */
int main()
{
int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
printTwoElements(arr, n);
}
// This code is contributed by Shivi_Aggarwal
C
// C program to Find the repeating
// and missing elements
#include <stdio.h>
#include <stdlib.h>
void printTwoElements(int arr[], int size)
{
int i;
printf("\nThe repeating element is ");
for (i = 0; i < size; i++) {
if (arr[abs(arr[i]) - 1] > 0)
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
else
printf(" %d ", abs(arr[i]));
}
printf("\nand the missing element is ");
for (i = 0; i < size; i++) {
if (arr[i] > 0)
printf("%d", i + 1);
}
}
// Driver code
int main()
{
int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
printTwoElements(arr, n);
return 0;
}
Java
// Java program to Find the repeating
// and missing elements
import java.io.*;
class GFG {
static void printTwoElements(int arr[], int size)
{
int i;
System.out.print("The repeating element is ");
for (i = 0; i < size; i++) {
int abs_val = Math.abs(arr[i]);
if (arr[abs_val - 1] > 0)
arr[abs_val - 1] = -arr[abs_val - 1];
else
System.out.println(abs_val);
}
System.out.print("and the missing element is ");
for (i = 0; i < size; i++) {
if (arr[i] > 0)
System.out.println(i + 1);
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
int n = arr.length;
printTwoElements(arr, n);
}
}
// This code is contributed by Gitanjali
Python3
# Python3 code to Find the repeating
# and the missing elements
def printTwoElements( arr, size):
for i in range(size):
if arr[abs(arr[i])-1] > 0:
arr[abs(arr[i])-1] = -arr[abs(arr[i])-1]
else:
print("The repeating element is ", abs(arr[i]))
for i in range(size):
if arr[i]>0:
print("and the missing element is ", i + 1)
# Driver program to test above function */
arr = [7, 3, 4, 5, 5, 6, 2]
n = len(arr)
printTwoElements(arr, n)
# This code is contributed by "Abhishek Sharma 44"
C#
// C# program to Find the repeating
// and missing elements
using System;
class GFG {
static void printTwoElements(int[] arr, int size)
{
int i;
Console.Write("The repeating element is ");
for (i = 0; i < size; i++) {
int abs_val = Math.Abs(arr[i]);
if (arr[abs_val - 1] > 0)
arr[abs_val - 1] = -arr[abs_val - 1];
else
Console.WriteLine(abs_val);
}
Console.Write("and the missing element is ");
for (i = 0; i < size; i++) {
if (arr[i] > 0)
Console.WriteLine(i + 1);
}
}
// Driver program
public static void Main()
{
int[] arr = { 7, 3, 4, 5, 5, 6, 2 };
int n = arr.Length;
printTwoElements(arr, n);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to Find the repeating
// and missing elements
function printTwoElements($arr, $size)
{
$i;
echo "The repeating element is", " ";
for($i = 0; $i < $size; $i++)
{
if($arr[abs($arr[$i]) - 1] > 0)
$arr[abs($arr[$i]) - 1] =
- $arr[abs($arr[$i]) - 1];
else
echo ( abs($arr[$i]));
}
echo "\nand the missing element is ";
for($i = 0; $i < $size; $i++)
{
if($arr[$i] > 0)
echo($i + 1);
}
}
// Driver Code
$arr = array(7, 3, 4, 5, 5, 6, 2);
$n = count($arr);
printTwoElements($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Program to Find the repeating
// and missing elements
function printTwoElements(arr,size)
{
var i;
document.write("The repeating element is ");
for (i = 0; i < size; i++)
{
var abs_value = Math.abs(arr[i]);
if (arr[abs_value - 1] > 0)
arr[abs_value - 1] = -arr[abs_value - 1];
else
document.write( abs_value);
}
document.write("<br> and the missing element is ");
for (i = 0; i < size; i++)
{
if (arr[i] > 0)
document.write (i + 1);
}
}
/* Driver code */
arr = new Array ( 7, 3, 4, 5, 5, 6, 2 );
n = arr.length;
printTwoElements(arr, n);
// This code is contributed by simranarora5sos
</script>
Producción
The repeating element is 5 and the missing element is 1
Complejidad de tiempo: O(n)
Gracias a Manish Mishra por sugerir este método.
Método 4 (Hacer dos ecuaciones)
Enfoque:
- Sea x el elemento que falta y y el elemento que se repite.
- Obtén la suma de todos los números usando la fórmula S = n(n+1)/2 – x + y
- Obtenga el producto de todos los números usando la fórmula P = 1*2*3*…*n * y / x
- Los dos pasos anteriores nos dan dos ecuaciones, podemos resolver las ecuaciones y obtener los valores de x e y.
Complejidad de tiempo: O(n)
Gracias a disabledng por sugerir esta solución.
Nota: este método puede causar un desbordamiento aritmético cuando calculamos el producto y la suma de todos los elementos de la array.
Método 5 (Usar XOR)
Acercarse:
- Sean x e y los elementos de salida deseados.
- Calcule XOR de todos los elementos de la array.
xor1 = arr[0]^arr[1]^arr[2]…..arr[n-1]
- XOR el resultado con todos los números del 1 al n
xor1 = xor1^1^2^…..^n
- En el resultado xor1 , todos los elementos se anularían entre sí excepto x e y. Todos los bits que se establecen en xor1 se establecerán en x o y. Entonces, si tomamos cualquier bit establecido (hemos elegido el bit establecido más a la derecha en el código) de xor1 y dividimos los elementos de la array en dos conjuntos: un conjunto de elementos con el mismo bit establecido y otro conjunto con el mismo bit no establecido. Al hacerlo, obtendremos x en un conjunto e y en otro conjunto. Ahora, si hacemos XOR de todos los elementos en el primer conjunto, obtendremos x, y al hacer lo mismo en otro conjunto obtendremos y.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Find the repeating
// and missing elements
#include <bits/stdc++.h>
using namespace std;
/* The output of this function is stored at
*x and *y */
void getTwoElements(int arr[], int n,
int* x, int* y)
{
/* Will hold xor of all elements
and numbers from 1 to n */
int xor1;
/* Will have only single set bit of xor1 */
int set_bit_no;
int i;
*x = 0;
*y = 0;
xor1 = arr[0];
/* Get the xor of all array elements */
for (i = 1; i < n; i++)
xor1 = xor1 ^ arr[i];
/* XOR the previous result with numbers
from 1 to n*/
for (i = 1; i <= n; i++)
xor1 = xor1 ^ i;
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor1 & ~(xor1 - 1);
/* Now divide elements into two
sets by comparing a rightmost set
bit of xor1 with the bit at the same
position in each element. Also,
get XORs of two sets. The two
XORs are the output elements.
The following two for loops
serve the purpose */
for (i = 0; i < n; i++) {
if (arr[i] & set_bit_no)
/* arr[i] belongs to first set */
*x = *x ^ arr[i];
else
/* arr[i] belongs to second set*/
*y = *y ^ arr[i];
}
for (i = 1; i <= n; i++) {
if (i & set_bit_no)
/* i belongs to first set */
*x = *x ^ i;
else
/* i belongs to second set*/
*y = *y ^ i;
}
/* *x and *y hold the desired
output elements */
}
/* Driver code */
int main()
{
int arr[] = { 1, 3, 4, 5, 5, 6, 2 };
int* x = (int*)malloc(sizeof(int));
int* y = (int*)malloc(sizeof(int));
int n = sizeof(arr) / sizeof(arr[0]);
getTwoElements(arr, n, x, y);
cout << " The missing element is " << *x << " and the repeating"
<< " number is " << *y;
getchar();
}
// This code is contributed by Code_Mech
C
// C program to Find the repeating
// and missing elements
#include <stdio.h>
#include <stdlib.h>
/* The output of this function is stored at
*x and *y */
void getTwoElements(int arr[], int n, int* x, int* y)
{
/* Will hold xor of all elements and numbers
from 1 to n */
int xor1;
/* Will have only single set bit of xor1 */
int set_bit_no;
int i;
*x = 0;
*y = 0;
xor1 = arr[0];
/* Get the xor of all array elements */
for (i = 1; i < n; i++)
xor1 = xor1 ^ arr[i];
/* XOR the previous result with numbers
from 1 to n*/
for (i = 1; i <= n; i++)
xor1 = xor1 ^ i;
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor1 & ~(xor1 - 1);
/* Now divide elements in two sets by comparing
rightmost set bit of xor1 with bit at same
position in each element. Also, get XORs of two
sets. The two XORs are the output elements. The
following two for loops serve the purpose */
for (i = 0; i < n; i++) {
if (arr[i] & set_bit_no)
/* arr[i] belongs to first set */
*x = *x ^ arr[i];
else
/* arr[i] belongs to second set*/
*y = *y ^ arr[i];
}
for (i = 1; i <= n; i++) {
if (i & set_bit_no)
/* i belongs to first set */
*x = *x ^ i;
else
/* i belongs to second set*/
*y = *y ^ i;
}
/* *x and *y hold the desired output elements */
}
/* Driver program to test above function */
int main()
{
int arr[] = { 1, 3, 4, 5, 5, 6, 2 };
int* x = (int*)malloc(sizeof(int));
int* y = (int*)malloc(sizeof(int));
int n = sizeof(arr) / sizeof(arr[0]);
getTwoElements(arr, n, x, y);
printf(" The missing element is %d"
" and the repeating number"
" is %d",
*x, *y);
getchar();
}
Java
// Java program to Find the repeating
// and missing elements
import java.io.*;
class GFG {
static int x, y;
static void getTwoElements(int arr[], int n)
{
/* Will hold xor of all elements
and numbers from 1 to n */
int xor1;
/* Will have only single set bit of xor1 */
int set_bit_no;
int i;
x = 0;
y = 0;
xor1 = arr[0];
/* Get the xor of all array elements */
for (i = 1; i < n; i++)
xor1 = xor1 ^ arr[i];
/* XOR the previous result with numbers from
1 to n*/
for (i = 1; i <= n; i++)
xor1 = xor1 ^ i;
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor1 & ~(xor1 - 1);
/* Now divide elements into two sets by comparing
rightmost set bit of xor1 with the bit at the same
position in each element. Also, get XORs of two
sets. The two XORs are the output elements. The
following two for loops serve the purpose */
for (i = 0; i < n; i++) {
if ((arr[i] & set_bit_no) != 0)
/* arr[i] belongs to first set */
x = x ^ arr[i];
else
/* arr[i] belongs to second set*/
y = y ^ arr[i];
}
for (i = 1; i <= n; i++) {
if ((i & set_bit_no) != 0)
/* i belongs to first set */
x = x ^ i;
else
/* i belongs to second set*/
y = y ^ i;
}
/* *x and *y hold the desired output elements */
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = { 1, 3, 4, 5, 1, 6, 2 };
int n = arr.length;
getTwoElements(arr, n);
System.out.println(" The missing element is "
+ x + "and the "
+ "repeating number is "
+ y);
}
}
// This code is contributed by Gitanjali.
Python3
# Python3 program to find the repeating
# and missing elements
# The output of this function is stored
# at x and y
def getTwoElements(arr, n):
global x, y
x = 0
y = 0
# Will hold xor of all elements
# and numbers from 1 to n
xor1 = arr[0]
# Get the xor of all array elements
for i in range(1, n):
xor1 = xor1 ^ arr[i]
# XOR the previous result with numbers
# from 1 to n
for i in range(1, n + 1):
xor1 = xor1 ^ i
# Will have only single set bit of xor1
set_bit_no = xor1 & ~(xor1 - 1)
# Now divide elements into two
# sets by comparing a rightmost set
# bit of xor1 with the bit at the same
# position in each element. Also,
# get XORs of two sets. The two
# XORs are the output elements.
# The following two for loops
# serve the purpose
for i in range(n):
if (arr[i] & set_bit_no) != 0:
# arr[i] belongs to first set
x = x ^ arr[i]
else:
# arr[i] belongs to second set
y = y ^ arr[i]
for i in range(1, n + 1):
if (i & set_bit_no) != 0:
# i belongs to first set
x = x ^ i
else:
# i belongs to second set
y = y ^ i
# x and y hold the desired
# output elements
# Driver code
arr = [ 1, 3, 4, 5, 5, 6, 2 ]
n = len(arr)
getTwoElements(arr, n)
print("The missing element is", x,
"and the repeating number is", y)
# This code is contributed by stutipathak31jan
C#
// C# program to Find the repeating
// and missing elements
using System;
class GFG {
static int x, y;
static void getTwoElements(int[] arr, int n)
{
/* Will hold xor of all elements
and numbers from 1 to n */
int xor1;
/* Will have only single set bit of xor1 */
int set_bit_no;
int i;
x = 0;
y = 0;
xor1 = arr[0];
/* Get the xor of all array elements */
for (i = 1; i < n; i++)
xor1 = xor1 ^ arr[i];
/* XOR the previous result with numbers from
1 to n*/
for (i = 1; i <= n; i++)
xor1 = xor1 ^ i;
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor1 & ~(xor1 - 1);
/* Now divide elements in two sets by comparing
rightmost set bit of xor1 with bit at same
position in each element. Also, get XORs of two
sets. The two XORs are the output elements.The
following two for loops serve the purpose */
for (i = 0; i < n; i++) {
if ((arr[i] & set_bit_no) != 0)
/* arr[i] belongs to first set */
x = x ^ arr[i];
else
/* arr[i] belongs to second set*/
y = y ^ arr[i];
}
for (i = 1; i <= n; i++) {
if ((i & set_bit_no) != 0)
/* i belongs to first set */
x = x ^ i;
else
/* i belongs to second set*/
y = y ^ i;
}
/* *x and *y hold the desired output elements */
}
// Driver program
public static void Main()
{
int[] arr = { 1, 3, 4, 5, 1, 6, 2 };
int n = arr.Length;
getTwoElements(arr, n);
Console.Write(" The missing element is "
+ x + "and the "
+ "repeating number is "
+ y);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to Find the repeating
// and missing elements
function getTwoElements(&$arr, $n)
{
/* Will hold xor of all elements
and numbers from 1 to n */
$xor1;
/* Will have only single set bit of xor1 */
$set_bit_no;
$i;
$x = 0;
$y = 0;
$xor1 = $arr[0];
/* Get the xor of all array elements */
for ($i = 1; $i < $n; $i++)
$xor1 = $xor1 ^ $arr[$i];
/* XOR the previous result with numbers
from 1 to n*/
for ($i = 1; $i <= $n; $i++)
$xor1 = $xor1 ^ $i;
/* Get the rightmost set bit in set_bit_no */
$set_bit_no = $xor1 & ~($xor1 - 1);
/* Now divide elements in two sets by comparing
rightmost set bit of xor1 with bit at same
position in each element. Also, get XORs of two
sets. The two XORs are the output elements.The
following two for loops serve the purpose */
for ($i = 0; $i < $n; $i++)
{
if (($arr[$i] & $set_bit_no) != 0)
/* arr[i] belongs to first set */
$x = $x ^ $arr[$i];
else
/* arr[i] belongs to second set*/
$y = $y ^ $arr[$i];
}
for ($i = 1; $i <= $n; $i++)
{
if (($i & $set_bit_no) != 0)
/* i belongs to first set */
$x = $x ^ $i;
else
/* i belongs to second set*/
$y = $y ^ $i;
}
/* *x and *y hold the desired output elements */
echo("The missing element is " . $x .
" and the repeating number is " . $y);
}
// Driver Code
$arr = array( 1, 3, 4, 5, 1, 6, 2 );
$n = sizeof($arr);
getTwoElements($arr, $n);
// This code is contributed by Code_Mech
Producción
The missing element is 7 and the repeating number is 5
Complejidad de tiempo: O(n)
Este método no causa desbordamiento, pero no dice cuál ocurre dos veces y cuál falta. Podemos agregar un paso más que verifique cuál falta y cuál se repite. Esto se puede hacer fácilmente en tiempo O(n).
Método 6 (usar un mapa)
Enfoque:
este método implica crear una tabla hash con la ayuda de Map. En esto, los elementos se asignan a su índice natural. En este proceso, si un elemento se mapea dos veces, entonces es el elemento repetido. Y si la asignación de un elemento no está allí, entonces es el elemento que falta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the repeating
// and missing elements using Maps
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
int arr[] = { 4, 3, 6, 2, 1, 1 };
int n = 6;
unordered_map<int, bool> numberMap;
for(int i : arr)
{
if (numberMap.find(i) ==
numberMap.end())
{
numberMap[i] = true;
}
else
{
cout << "Repeating = " << i;
}
}
cout << endl;
for(int i = 1; i <= n; i++)
{
if (numberMap.find(i) ==
numberMap.end())
{
cout << "Missing = " << i;
}
}
return 0;
}
// This code is contributed by RohitOberoi
Java
// Java program to find the
// repeating and missing elements
// using Maps
import java.util.*;
public class Test1 {
public static void main(String[] args)
{
int[] arr = { 4, 3, 6, 2, 1, 1 };
Map<Integer, Boolean> numberMap
= new HashMap<>();
int max = arr.length;
for (Integer i : arr) {
if (numberMap.get(i) == null) {
numberMap.put(i, true);
}
else {
System.out.println("Repeating = " + i);
}
}
for (int i = 1; i <= max; i++) {
if (numberMap.get(i) == null) {
System.out.println("Missing = " + i);
}
}
}
}
Python3
# Python3 program to find the
# repeating and missing elements
# using Maps
def main():
arr = [ 4, 3, 6, 2, 1, 1 ]
numberMap = {}
max = len(arr)
for i in arr:
if not i in numberMap:
numberMap[i] = True
else:
print("Repeating =", i)
for i in range(1, max + 1):
if not i in numberMap:
print("Missing =", i)
main()
# This code is contributed by stutipathak31jan
C#
// C# program to find the
// repeating and missing elements
// using Maps
using System;
using System.Collections.Generic;
class GFG
{
public static void Main(String[] args)
{
int[] arr = { 4, 3, 6, 2, 1, 1 };
Dictionary<int, Boolean> numberMap =
new Dictionary<int, Boolean>();
int max = arr.Length;
foreach (int i in arr)
{
if (!numberMap.ContainsKey(i))
{
numberMap.Add(i, true);
}
else
{
Console.WriteLine("Repeating = " + i);
}
}
for (int i = 1; i <= max; i++)
{
if (!numberMap.ContainsKey(i))
{
Console.WriteLine("Missing = " + i);
}
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find the repeating
// and missing elements using Maps
// driver program
let arr = [ 4, 3, 6, 2, 1, 1 ];
let n = 6;
let numberMap = new Map();
for(let i of arr)
{
if (numberMap.has(i) == false) {
numberMap.set(i,true);
}
else
{
document.write("Repeating = ",i);
}
}
document.write("</br>");
for(let i = 1; i <= n; i++)
{
if (numberMap.has(i) == false) {
document.write("Missing = " ,i);
}
}
// This code is contributed by Shinjanpatra
</script>
Producción
Repeating = 1 Missing = 5
Método 7 (Hacer dos ecuaciones usando suma y suma de cuadrados)
Enfoque:
- Sea x el elemento que falta y y el elemento que se repite.
- Sea N el tamaño de la array.
- Obtén la suma de todos los números usando la fórmula S = N(N+1)/2
- Obtenga la suma de los cuadrados de todos los números usando la fórmula Sum_Sq = N(N+1)(2N+1)/6
- Iterar a través de un ciclo desde i=1….N
- S-=A[i]
- Suma_Sq -= (A[i]*A[i])
- Dará dos ecuaciones
xy = S – (1)
x^2 – y^2 = Sum_sq
x+ y = (Sum_sq/S) – (2)
Complejidad de tiempo: O(n)
C++
#include <bits/stdc++.h>
using namespace std;
vector<int>repeatedNumber(const vector<int> &A) {
long long int len = A.size();
long long int Sum_N = (len * (len+1) ) /2, Sum_NSq = (len * (len +1) *(2*len +1) )/6;
long long int missingNumber=0, repeating=0;
for(int i=0;i<A.size(); i++){
Sum_N -= (long long int)A[i];
Sum_NSq -= (long long int)A[i]*(long long int)A[i];
}
missingNumber = (Sum_N + Sum_NSq/Sum_N)/2;
repeating= missingNumber - Sum_N;
vector <int> ans;
ans.push_back(repeating);
ans.push_back(missingNumber);
return ans;
}
int main(void){
std::vector<int> v = {4, 3, 6, 2, 1, 6,7};
vector<int> res = repeatedNumber(v);
for(int x: res){
cout<< x<<" ";
}
cout<<endl;
}
Java
import java.util.*;
import java.math.BigInteger;
class GFG
{
static Vector<Integer> repeatedNumber(int[] a)
{
BigInteger n=BigInteger.valueOf(a.length);
BigInteger s=BigInteger.valueOf(0);
BigInteger ss=BigInteger.valueOf(0);
for(int x : a)
{
s= s.add(BigInteger.valueOf(x));
ss= ss.add(BigInteger.valueOf(x).multiply(BigInteger.valueOf(x)));
}
BigInteger as= n.multiply(n.add(BigInteger.valueOf(1))).divide(BigInteger.valueOf(2));
BigInteger ass= as.multiply(BigInteger.valueOf(2).multiply(n).add(BigInteger.valueOf(1))).divide(BigInteger.valueOf(3));
BigInteger sub=as.subtract(s);
BigInteger add=(ass.subtract(ss)).divide(sub);
//(ass-ss)/sub;
int b = sub.add(add).divide(BigInteger.valueOf(2)).intValue();
//(sub+add)/2;
int A = BigInteger.valueOf(b).subtract(sub).intValue();
Vector<Integer> ans = new Vector<>();
ans.add(A);
ans.add(b);
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] v = { 4, 3, 6, 2, 1, 6, 7 };
Vector<Integer> res = repeatedNumber(v);
for (int x : res)
{
System.out.print(x + " ");
}
}
}
// This code is contributed by Rajput-Ji
Python3
def repeatedNumber(A): length = len(A) Sum_N = (length * (length + 1)) // 2 Sum_NSq = ((length * (length + 1) * (2 * length + 1)) // 6) missingNumber, repeating = 0, 0 for i in range(len(A)): Sum_N -= A[i] Sum_NSq -= A[i] * A[i] missingNumber = (Sum_N + Sum_NSq // Sum_N) // 2 repeating = missingNumber - Sum_N ans = [] ans.append(repeating) ans.append(missingNumber) return ans # Driver code v = [ 4, 3, 6, 2, 1, 6, 7 ] res = repeatedNumber(v) for i in res: print(i, end = " ") # This code is contributed by stutipathak31jan
C#
using System;
using System.Collections.Generic;
class GFG
{
static List<int> repeatedNumber(int[] A)
{
int len = A.Length;
int Sum_N = (len * (len + 1)) / 2;
int Sum_NSq = (len * (len + 1) *
(2 * len + 1)) / 6;
int missingNumber = 0, repeating = 0;
for (int i = 0; i < A.Length; i++)
{
Sum_N -= A[i];
Sum_NSq -= A[i] * A[i];
}
missingNumber = (Sum_N + Sum_NSq /
Sum_N) / 2;
repeating = missingNumber - Sum_N;
List<int> ans = new List<int>();
ans.Add(repeating);
ans.Add(missingNumber);
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int[] v = { 4, 3, 6, 2, 1, 6, 7 };
List<int> res = repeatedNumber(v);
foreach (int x in res)
{
Console.Write(x + " ");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
function repeatedNumber(A){
let length = A.length
let Sum_N = Math.floor((length * (length + 1)) / 2)
let Sum_NSq = Math.floor((length * (length + 1) * (2 * length + 1))/6)
let missingNumber = 0
let repeating = 0
for(let i=0;i<A.length;i++){
Sum_N -= A[i]
Sum_NSq -= A[i] * A[i]
}
missingNumber = Math.floor(Math.floor(Sum_N + Sum_NSq / Sum_N) / 2)
repeating = missingNumber - Sum_N
let ans = []
ans.push(repeating)
ans.push(missingNumber)
return ans
}
// Driver code
let v = [ 4, 3, 6, 2, 1, 6, 7 ]
let res = repeatedNumber(v)
for(let i of res)
document.write(i," ")
// This code is contributed by shinjanpatra
</script>
Producción
6 5
Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra otras formas de resolver el mismo problema.
Método 8 (usando el operador OR):
Gracias a Anish Shaha por sugerir este método.
Acercarse:
Dada una array de entrada
- Realizando la operación OR en la array de entrada.
- Al mismo tiempo, comprobar si ese número se ha producido antes, determinando si la posición ya está configurada o no. Obtendremos el número repetido en este paso.
- Para encontrar el valor faltante, debemos verificar el bit que contiene 0 usando OR nuevamente.
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
// Input:
vector<int> arr = { 4, 3, 6, 2, 1, 1 };
int n = arr.size();
// Declaring output variables
// Note : arr[i]-1 is used instead of arr[i] as we want
// to use all 64 bits
int bitOr = (1 << (arr[0] - 1));
int repeating, missing;
// Performing XOR as well as Checking repeating number
for (int i = 1; i < n; i++) {
// If OR operation with 1 gives same output that
// means, we already have 1 at that position
if ((bitOr | (1 << (arr[i] - 1))) == bitOr) {
repeating = arr[i];
continue;
}
bitOr = (bitOr | (1 << (arr[i] - 1)));
}
// Checking missing number
for (int i = 0; i < n; i++) {
// property: OR with 0 yield 1 hence value of bitOr
// changes
if ((bitOr | (1 << i)) != bitOr) {
missing = i + 1;
break;
}
}
cout << "Repeating : " << repeating
<< "\nMissing : " << missing;
return 0;
}
Java
import java.util.*;
class GFG{
public static void main(String[] args)
{
// Input:
int[] arr = {4, 3, 6, 2, 1, 1};
int n = arr.length;
// Declaring output variables
// Note : arr[i]-1 is used instead of arr[i] as we want to use all 64 bits
int bitOr = (1 << (arr[0]-1));
int repeating = 0, missing = 0;
// Performing XOR as well as Checking repeating number
for(int i=1; i<n; i++){
// If OR operation with 1 gives same output that means, we already have 1 at that position
if((bitOr | (1 << (arr[i]-1))) == bitOr) {
repeating = arr[i];
continue;
}
bitOr = (bitOr | (1 << (arr[i]-1)));
}
// Checking missing number
for(int i = 0; i < n; i++)
{
// property: OR with 0 yield 1 hence value of bitOr changes
if((bitOr | (1 << i)) != bitOr) {
missing = i+1;
break;
}
}
System.out.print("Repeating : " + repeating+ "\nMissing : " + missing);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python code for the above approach
class GFG:
def main(args):
# Input:
arr = [4, 3, 6, 2, 1, 1]
n = len(arr)
# Declaring output variables
# Note : arr[i]-1 is used instead of arr[i] as we want to use all 64 bits
bitOr = (1 << (arr[0] - 1))
repeating = 0
missing = 0
# Performing XOR as well as Checking repeating number
for i in range(1, n):
# If OR operation with 1 gives same output
# that means, we already have 1 at that position
if ((bitOr | (1 << (arr[i] - 1))) == bitOr):
repeating = arr[i]
continue
bitOr = (bitOr | (1 << (arr[i] - 1)))
# Checking missing number
for i in range(1, n):
# property: OR with 0 yield 1 hence value of bitOr changes
if ((bitOr | (1 << i)) != bitOr):
missing = i + 1
break
print("Repeating : " + str(repeating) + "\nMissing : " + str(missing))
if __name__ == "__main__":
GFG.main([])
# This code is contributed by Mukul Jatav (mukulsomukesh)
C#
using System;
public class GFG
{
public static void Main(String[] args)
{
// Input:
int[] arr = { 4, 3, 6, 2, 1, 1 };
int n = arr.Length;
// Declaring output variables
// Note : arr[i]-1 is used instead of arr[i] as we want to use all 64 bits
int bitOr = (1 << (arr[0] - 1));
int repeating = 0, missing = 0;
// Performing XOR as well as Checking repeating number
for (int i = 1; i < n; i++) {
// If OR operation with 1 gives same output that means, we already have 1 at
// that position
if ((bitOr | (1 << (arr[i] - 1))) == bitOr) {
repeating = arr[i];
continue;
}
bitOr = (bitOr | (1 << (arr[i] - 1)));
}
// Checking missing number
for (int i = 0; i < n; i++) {
// property: OR with 0 yield 1 hence value of bitOr changes
if ((bitOr | (1 << i)) != bitOr) {
missing = i + 1;
break;
}
}
Console.Write("Repeating : " + repeating + "\nMissing : " + missing);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
// Driver Code
// Input:
let arr = [4, 3, 6, 2, 1, 1];
let n = arr.length;
// Declaring output variables
// Note : arr[i]-1 is used instead of arr[i] as we want to use all 64 bits
let bitOr = (1 << (arr[0]-1));
let repeating = 0, missing = 0;
// Performing XOR as well as Checking repeating number
for(let i=1; i<n; i++){
// If OR operation with 1 gives same output that means, we already have 1 at that position
if((bitOr | (1 << (arr[i]-1))) == bitOr) {
repeating = arr[i];
continue;
}
bitOr = (bitOr | (1 << (arr[i]-1)));
}
// Checking missing number
for(let i = 0; i < n; i++)
{
// property: OR with 0 yield 1 hence value of bitOr changes
if((bitOr | (1 << i)) != bitOr) {
missing = i+1;
break;
}
}
document.write("Repeating : " + repeating+ "<br/>" + "Missing : " + missing);
// This code is contributed by code_hunt.
</script>
Producción
Repeating : 1 Missing : 5
Complejidad temporal : O(n) Espacio
auxiliar O(1)
Limitaciones del enfoque : solo funciona en el tamaño de la array <= 64 si usamos long y el tamaño de la array <= 32
Método 9: (Colocar cada elemento en su posición correcta)
Enfoque: Está claro a partir de la observación que si ordenamos una array, entonces arr[i] == i+1 . Si todos los elementos de una array cumplen esta condición, significa que este es un caso ideal. Entonces, la idea es ordenar la array dada y recorrerla y verificar si arr[i] == i + 1 , si es así, entonces incremente i (porque este elemento está en su posición correcta), de lo contrario, coloque este elemento (arr[i] ) en su posición correcta (arr[arr[i] – 1) intercambiando arr[i] y arr[arr[i] -1]. Este intercambio pondrá el elemento arr[i] en su posición correcta (es decir, arr[arr[i]-1]). Después de hacer esta operación, se superan todos los elementos de la array dada, luego nuevamente recorre la array y verifica si arr[i] != i + 1 si es así, entonces este es el elemento duplicado e i + 1 es el elemento faltante.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the missing
// and repeating element
#include <bits/stdc++.h>
using namespace std;
void getTwoElements(int arr[], int n)
{
int repeating(0), missing(0);
int i = 0;
// Traverse on the array
while (i < n)
{
// If the element is on its correct position
if (arr[i] == arr[arr[i] - 1])
i++;
// If it is not at its correct position
// then palce it to its correct position
else
swap(arr[i], arr[arr[i] - 1]);
}
// Find repeating and missing
for (int i = 0; i < n; i++) {
// If any element is not in its correct position
if (arr[i] != i + 1) {
repeating = arr[i];
missing = i + 1;
break;
}
}
// Print answer
cout << "Repeating: " << repeating << endl
<< "Missing: " << missing << endl;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 1, 5, 1 };
int n = sizeof(arr) / sizeof(int);
getTwoElements(arr, n);
return 0;
}
// This code is contributed by Tapesh (tapeshdua420)
Java
// Java program to find the missing
// and repeating element
import java.io.*;
public class Main {
static void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// Function to find the repeating and missing element
static void getTwoElements(int[] arr, int n)
{
int repeating = 0;
int missing = 0;
int i = 0;
// Traverse on the array
while (i < n) {
// If the element is on its correct position
if (arr[i] == arr[arr[i] - 1]) {
i++;
}
// If it is not at its correct position then
// place it to its correct position.
else {
swap(arr, i, arr[i] - 1);
}
}
// Find repeating and missing element.
for (i = 0; i < n; i++) {
// If any element is not in its correct position
if (arr[i] != i + 1) {
repeating = arr[i];
missing = i + 1;
break;
}
}
// Print answer
System.out.println("Repeating: " + repeating
+ "\nMissing: " + missing);
}
public static void main(String[] args)
{
int[] arr = { 2, 3, 1, 5, 1 };
int n = arr.length;
getTwoElements(arr, n);
}
}
// This code is contributed by Tapesh (tapeshdua420)
Python3
# Python program to find the missing
# and repeating element
def swap(arr, a, b):
temp = arr[a]
arr[a] = arr[b]
arr[b] = temp
def getTwoElements(arr, n):
repeating = 0
missing = 0
i = 0
# Traverse on the array
while (i < n):
# If the element is on its correct position
if (arr[i] == arr[arr[i] - 1]):
i += 1
else:
# If it is not at its correct position
# then palce it to its correct position
swap(arr, i, arr[i] - 1)
# Find repeating and missing
for i in range(n):
# If any element is not in its correct position
if (arr[i] != i + 1):
repeating = arr[i]
missing = i + 1
break
# Print answer
print("Repeating:", repeating)
print("Missing:", missing)
# Driver code
arr = [2, 3, 1, 5, 1]
n = len(arr)
getTwoElements(arr, n)
# This code is contributed by Tapesh (tapeshdua420)
C#
// C# program to find the missing
// and repeating element
using System;
class GFG
{
static void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// Function to find the repeating and missing element
static void getTwoElements(int[] arr, int n)
{
int repeating = 0;
int missing = 0;
int i = 0;
// Traverse on the array
while (i < n)
{
// If the element is on its correct position
if (arr[i] == arr[arr[i] - 1]) {
i++;
}
// If it is not at its correct position then
// place it to its correct position.
else
{
swap(arr, i, arr[i] - 1);
}
}
// Find repeating and missing element.
for (i = 0; i < n; i++)
{
// If any element is not in its correct position
if (arr[i] != i + 1) {
repeating = arr[i];
missing = i + 1;
break;
}
}
// Print answer
Console.Write("Repeating : " + repeating + "\nMissing : " + missing);
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 2, 3, 1, 5, 1 };
int n =arr.Length;
getTwoElements(arr,n);
}
}
// This code has been contributed by Aarti_Rathi
Javascript
<script>
// Javascript program to find the missing
// and repeating element
function swap(arr, a, b) {
let temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// Function to find the repeating and missing element
function getTwoElements(arr, n) {
let repeating = 0;
let missing = 0;
let i = 0;
// Traverse on the array
while (i < n) {
// If the element is on its correct position
if (arr[i] == arr[arr[i] - 1]) {
i++;
}
// If it is not at its correct position then
// place it to its correct position.
else {
swap(arr, i, arr[i] - 1);
}
}
// Find repeating and missing element.
for (i = 0; i < n; i++) {
// If any element is not in its correct position
if (arr[i] != i + 1) {
repeating = arr[i];
missing = i + 1;
break;
}
}
// Print answer
document.write("Repeating: " + repeating + "<br>Missing: " + missing);
}
let arr = [2, 3, 1, 5, 1];
let n = arr.length;
getTwoElements(arr, n);
// This code is contributed by gfgking
</script>
Producción
Repeating: 1 Missing: 4
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
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