Dada una array donde cada elemento aparece tres veces, excepto un elemento que aparece solo una vez. Encuentra el elemento que ocurre una vez. La complejidad temporal esperada es O(n) y O(1) espacio extra.
Ejemplos:
Entrada: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Salida: 2
En la array dada, todos los elementos aparecen tres veces excepto 2, que aparece una vez.Entrada: arr[] = {10, 20, 10, 30, 10, 30, 30}
Salida: 20
En la array dada, todos los elementos aparecen tres veces excepto 20 que aparece una vez.
Podemos usar la clasificación para hacerlo en tiempo O (nLogn). También podemos usar hashing, tiene la complejidad de tiempo en el peor de los casos de O (n), pero requiere espacio adicional.
La idea es usar operadores bit a bit para una solución que es O(n) tiempo y usa O(1) espacio extra. La solución no es fácil como otras soluciones basadas en XOR, porque aquí todos los elementos aparecen un número impar de veces. La idea está tomada de aquí .
Ejecute un bucle para todos los elementos de la array. Al final de cada iteración, mantenga los siguientes dos valores.
unos: Los bits que han aparecido la 1ª vez o la 4ª vez o la 7ª vez… etc.
doses: Los bits que han aparecido la 2ª vez o la 5ª vez o la 8ª vez…
etc.
¿Cómo mantener los valores de ‘unos’ y ‘dos’?
‘unos’ y ‘dos’ se inicializan como 0. Para cada elemento nuevo en la array, averigüe los bits establecidos comunes en el nuevo elemento y el valor anterior de ‘unos’. Estos bits establecidos comunes son en realidad los bits que deben agregarse a ‘dos’. Así que haga XOR bit a bit de los bits de conjunto comunes con ‘dos’. ‘dos’ también obtiene algunos bits adicionales que aparecen la tercera vez. Estos bits adicionales se eliminan más tarde.
Actualice ‘unos’ haciendo XOR del nuevo elemento con el valor anterior de ‘unos’. Puede haber algunos bits que aparezcan por tercera vez. Estos bits adicionales también se eliminan más tarde.
Tanto los ‘unos’ como los ‘dos’ contienen esos bits adicionales que aparecen por tercera vez. Elimine estos bits adicionales descubriendo los bits establecidos comunes en ‘unos’ y ‘dos’.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the element
// that occur only once
#include <bits/stdc++.h>
using namespace std;
int getSingle(int arr[], int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
// Let us take the example of
// {3, 3, 2, 3} to understand
// this
for (int i = 0; i < n; i++) {
/* The expression "one & arr[i]" gives the bits that
are there in both 'ones' and new element from arr[].
We add these bits to 'twos' using bitwise OR
Value of 'twos' will be set as 0, 3, 3 and 1 after
1st, 2nd, 3rd and 4th iterations respectively */
twos = twos | (ones & arr[i]);
/* XOR the new bits with previous 'ones' to get all
bits appearing odd number of times
Value of 'ones' will be set as 3, 0, 2 and 3 after
1st, 2nd, 3rd and 4th iterations respectively */
ones = ones ^ arr[i];
/* The common bits are those bits which appear third
time So these bits should not be there in both
'ones' and 'twos'. common_bit_mask contains all
these bits as 0, so that the bits can be removed
from 'ones' and 'twos'
Value of 'common_bit_mask' will be set as 00, 00, 01
and 10 after 1st, 2nd, 3rd and 4th iterations
respectively */
common_bit_mask = ~(ones & twos);
/* Remove common bits (the bits that appear third
time) from 'ones'
Value of 'ones' will be set as 3, 0, 0 and 2 after
1st, 2nd, 3rd and 4th iterations respectively */
ones &= common_bit_mask;
/* Remove common bits (the bits that appear third
time) from 'twos'
Value of 'twos' will be set as 0, 3, 1 and 0 after
1st, 2nd, 3rd and 4th iterations respectively */
twos &= common_bit_mask;
// uncomment this code to see intermediate values
// printf (" %d %d n", ones, twos);
}
return ones;
}
// Driver code
int main()
{
int arr[] = { 3, 3, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The element with single occurrence is "
<< getSingle(arr, n);
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to find the element
// that occur only once
#include <stdio.h>
int getSingle(int arr[], int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
// Let us take the example of {3, 3, 2, 3} to understand this
for (int i = 0; i < n; i++) {
/* The expression "one & arr[i]" gives the bits that are
there in both 'ones' and new element from arr[]. We
add these bits to 'twos' using bitwise OR
Value of 'twos' will be set as 0, 3, 3 and 1 after 1st,
2nd, 3rd and 4th iterations respectively */
twos = twos | (ones & arr[i]);
/* XOR the new bits with previous 'ones' to get all bits
appearing odd number of times
Value of 'ones' will be set as 3, 0, 2 and 3 after 1st,
2nd, 3rd and 4th iterations respectively */
ones = ones ^ arr[i];
/* The common bits are those bits which appear third time
So these bits should not be there in both 'ones' and 'twos'.
common_bit_mask contains all these bits as 0, so that the bits can
be removed from 'ones' and 'twos'
Value of 'common_bit_mask' will be set as 00, 00, 01 and 10
after 1st, 2nd, 3rd and 4th iterations respectively */
common_bit_mask = ~(ones & twos);
/* Remove common bits (the bits that appear third time) from 'ones'
Value of 'ones' will be set as 3, 0, 0 and 2 after 1st,
2nd, 3rd and 4th iterations respectively */
ones &= common_bit_mask;
/* Remove common bits (the bits that appear third time) from 'twos'
Value of 'twos' will be set as 0, 3, 1 and 0 after 1st,
2nd, 3rd and 4th iterations respectively */
twos &= common_bit_mask;
// uncomment this code to see intermediate values
// printf (" %d %d n", ones, twos);
}
return ones;
}
int main()
{
int arr[] = { 3, 3, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}
Java
// Java code to find the element
// that occur only once
class GFG {
// Method to find the element that occur only once
static int getSingle(int arr[], int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
for (int i = 0; i < n; i++) {
/*"one & arr[i]" gives the bits that are there in
both 'ones' and new element from arr[]. We
add these bits to 'twos' using bitwise OR*/
twos = twos | (ones & arr[i]);
/*"one & arr[i]" gives the bits that are
there in both 'ones' and new element from arr[].
We add these bits to 'twos' using bitwise OR*/
ones = ones ^ arr[i];
/* The common bits are those bits which appear third time
So these bits should not be there in both 'ones' and 'twos'.
common_bit_mask contains all these bits as 0, so that the bits can
be removed from 'ones' and 'twos'*/
common_bit_mask = ~(ones & twos);
/*Remove common bits (the bits that appear third time) from 'ones'*/
ones &= common_bit_mask;
/*Remove common bits (the bits that appear third time) from 'twos'*/
twos &= common_bit_mask;
}
return ones;
}
// Driver method
public static void main(String args[])
{
int arr[] = { 3, 3, 2, 3 };
int n = arr.length;
System.out.println("The element with single occurrence is " + getSingle(arr, n));
}
}
// Code contributed by Rishab Jain
Python3
# Python3 code to find the element that
# appears once
def getSingle(arr, n):
ones = 0
twos = 0
for i in range(n):
# one & arr[i]" gives the bits that
# are there in both 'ones' and new
# element from arr[]. We add these
# bits to 'twos' using bitwise XOR
twos = twos ^ (ones & arr[i])
# one & arr[i]" gives the bits that
# are there in both 'ones' and new
# element from arr[]. We add these
# bits to 'twos' using bitwise XOR
ones = ones ^ arr[i]
# The common bits are those bits
# which appear third time. So these
# bits should not be there in both
# 'ones' and 'twos'. common_bit_mask
# contains all these bits as 0, so
# that the bits can be removed from
# 'ones' and 'twos'
common_bit_mask = ~(ones & twos)
# Remove common bits (the bits that
# appear third time) from 'ones'
ones &= common_bit_mask
# Remove common bits (the bits that
# appear third time) from 'twos'
twos &= common_bit_mask
return ones
# driver code
arr = [3, 3, 2, 3]
n = len(arr)
print("The element with single occurrence is ",
getSingle(arr, n))
# This code is contributed by "Abhishek Sharma 44"
C#
// C# code to find the element
// that occur only once
using System;
class GFG {
// Method to find the element
// that occur only once
static int getSingle(int[] arr, int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
for (int i = 0; i < n; i++) {
// "one & arr[i]" gives the bits
// that are there in both 'ones'
// and new element from arr[].
// We add these bits to 'twos'
// using bitwise OR
twos = twos | (ones & arr[i]);
// "one & arr[i]" gives the bits
// that are there in both 'ones'
// and new element from arr[].
// We add these bits to 'twos'
// using bitwise OR
ones = ones ^ arr[i];
// The common bits are those bits
// which appear third time So these
// bits should not be there in both
// 'ones' and 'twos'. common_bit_mask
// contains all these bits as 0,
// so that the bits can be removed
// from 'ones' and 'twos'
common_bit_mask = ~(ones & twos);
// Remove common bits (the bits that
// appear third time) from 'ones'
ones &= common_bit_mask;
// Remove common bits (the bits that
// appear third time) from 'twos'
twos &= common_bit_mask;
}
return ones;
}
// Driver code
public static void Main()
{
int[] arr = { 3, 3, 2, 3 };
int n = arr.Length;
Console.WriteLine("The element with single"
+ "occurrence is " + getSingle(arr, n));
}
}
// This Code is contributed by vt_m.
PHP
<?php
// PHP program to find the element
// that occur only once
function getSingle($arr, $n)
{
$ones = 0; $twos = 0 ;
$common_bit_mask;
// Let us take the example of
// {3, 3, 2, 3} to understand this
for($i = 0; $i < $n; $i++ )
{
/* The expression "one & arr[i]"
gives the bits that are there in
both 'ones' and new element from
arr[]. We add these bits to 'twos'
using bitwise OR
Value of 'twos' will be set as 0,
3, 3 and 1 after 1st, 2nd, 3rd
and 4th iterations respectively */
$twos = $twos | ($ones & $arr[$i]);
/* XOR the new bits with previous
'ones' to get all bits appearing
odd number of times
Value of 'ones' will be set as 3,
0, 2 and 3 after 1st, 2nd, 3rd and
4th iterations respectively */
$ones = $ones ^ $arr[$i];
/* The common bits are those bits
which appear third time. So these
bits should not be there in both
'ones' and 'twos'. common_bit_mask
contains all these bits as 0, so
that the bits can be removed from
'ones' and 'twos'
Value of 'common_bit_mask' will be
set as 00, 00, 01 and 10 after 1st,
2nd, 3rd and 4th iterations respectively */
$common_bit_mask = ~($ones & $twos);
/* Remove common bits (the bits
that appear third time) from 'ones'
Value of 'ones' will be set as 3,
0, 0 and 2 after 1st, 2nd, 3rd
and 4th iterations respectively */
$ones &= $common_bit_mask;
/* Remove common bits (the bits
that appear third time) from 'twos'
Value of 'twos' will be set as 0, 3,
1 and 0 after 1st, 2nd, 3rd and 4th
iterations respectively */
$twos &= $common_bit_mask;
// uncomment this code to see
// intermediate values
// printf (" %d %d n", ones, twos);
}
return $ones;
}
// Driver Code
$arr = array(3, 3, 2, 3);
$n = sizeof($arr);
echo "The element with single " .
"occurrence is ",
getSingle($arr, $n);
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program for the above approach
// Method to find the element that occur only once
function getSingle(arr, n)
{
let ones = 0, twos = 0;
let common_bit_mask;
for (let i = 0; i < n; i++) {
/*"one & arr[i]" gives the bits that are there in
both 'ones' and new element from arr[]. We
add these bits to 'twos' using bitwise OR*/
twos = twos | (ones & arr[i]);
/*"one & arr[i]" gives the bits that are
there in both 'ones' and new element from arr[].
We add these bits to 'twos' using bitwise OR*/
ones = ones ^ arr[i];
/* The common bits are those bits which appear third time
So these bits should not be there in both 'ones' and 'twos'.
common_bit_mask contains all these bits as 0, so that the bits can
be removed from 'ones' and 'twos'*/
common_bit_mask = ~(ones & twos);
/*Remove common bits (the bits that appear third time) from 'ones'*/
ones &= common_bit_mask;
/*Remove common bits (the bits that appear third time) from 'twos'*/
twos &= common_bit_mask;
}
return ones;
}
// Driver Code
let arr = [ 3, 3, 2, 3 ];
let n = arr.length;
document.write("The element with single occurrence is " + getSingle(arr, n));
</script>
Producción
The element with single occurrence is 2
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Lo siguiente es otro método de complejidad de tiempo O(n) y espacio extra O(1) sugerido por aj . Podemos sumar los bits en las mismas posiciones para todos los números y tomar módulo con 3. Los bits para los cuales la suma no es múltiplo de 3, son los bits de número con ocurrencia única.
Consideremos la array de ejemplo {5, 5, 5, 8}. Los 101, 101, 101, 1000
Suma de primeros bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Suma de segundos bits%3 = (0 + 0 + 0 + 0)%3 = 0;
Suma de terceros bits%3 = (1 + 1 + 1 + 0)%3 = 0;
Suma de cuartos bits%3 = (1)%3 = 1;
Por lo tanto, el número que aparece una vez es 1000
Nota: este enfoque no funcionará para números negativos
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the element
// that occur only once
#include <bits/stdc++.h>
using namespace std;
#define INT_SIZE 32
int getSingle(int arr[], int n)
{
// Initialize result
int result = 0;
int x, sum;
// Iterate through every bit
for (int i = 0; i < INT_SIZE; i++) {
// Find sum of set bits at ith position in all
// array elements
sum = 0;
x = (1 << i);
for (int j = 0; j < n; j++) {
if (arr[j] & x)
sum++;
}
// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if ((sum % 3) != 0)
result |= x;
}
return result;
}
// Driver code
int main()
{
int arr[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The element with single occurrence is " << getSingle(arr, n);
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to find the element
// that occur only once
#include <stdio.h>
#define INT_SIZE 32
int getSingle(int arr[], int n)
{
// Initialize result
int result = 0;
int x, sum;
// Iterate through every bit
for (int i = 0; i < INT_SIZE; i++) {
// Find sum of set bits at ith position in all
// array elements
sum = 0;
x = (1 << i);
for (int j = 0; j < n; j++) {
if (arr[j] & x)
sum++;
}
// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if ((sum % 3) != 0)
result |= x;
}
return result;
}
// Driver program to test above function
int main()
{
int arr[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The element with single occurrence is %d ",
getSingle(arr, n));
return 0;
}
Java
// Java code to find the element
// that occur only once
class GFG {
static final int INT_SIZE = 32;
// Method to find the element that occur only once
static int getSingle(int arr[], int n)
{
int result = 0;
int x, sum;
// Iterate through every bit
for (int i = 0; i < INT_SIZE; i++) {
// Find sum of set bits at ith position in all
// array elements
sum = 0;
x = (1 << i);
for (int j = 0; j < n; j++) {
if ((arr[j] & x) != 0)
sum++;
}
// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if ((sum % 3) != 0)
result |= x;
}
return result;
}
// Driver method
public static void main(String args[])
{
int arr[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 };
int n = arr.length;
System.out.println("The element with single occurrence is " + getSingle(arr, n));
}
}
// Code contributed by Rishab Jain
Python3
# Python3 code to find the element
# that occur only once
INT_SIZE = 32
def getSingle(arr, n) :
# Initialize result
result = 0
# Iterate through every bit
for i in range(0, INT_SIZE) :
# Find sum of set bits
# at ith position in all
# array elements
sm = 0
x = (1 << i)
for j in range(0, n) :
if (arr[j] & x) :
sm = sm + 1
# The bits with sum not
# multiple of 3, are the
# bits of element with
# single occurrence.
if ((sm % 3)!= 0) :
result = result | x
return result
# Driver program
arr = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
n = len(arr)
print("The element with single occurrence is ", getSingle(arr, n))
# This code is contributed
# by Nikita Tiwari.
C#
// C# code to find the element
// that occur only once
using System;
class GFG {
static int INT_SIZE = 32;
// Method to find the element
// that occur only once
static int getSingle(int[] arr, int n)
{
int result = 0;
int x, sum;
// Iterate through every bit
for (int i = 0; i < INT_SIZE; i++) {
// Find sum of set bits at ith
// position in all array elements
sum = 0;
x = (1 << i);
for (int j = 0; j < n; j++) {
if ((arr[j] & x) != 0)
sum++;
}
// The bits with sum not multiple
// of 3, are the bits of element
// with single occurrence.
if ((sum % 3) != 0)
result |= x;
}
return result;
}
// Driver Code
public static void Main()
{
int[] arr = { 12, 1, 12, 3, 12, 1,
1, 2, 3, 2, 2, 3, 7 };
int n = arr.Length;
Console.WriteLine("The element with single "
+ "occurrence is " + getSingle(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP code to find the element
// that occur only once
$INT_SIZE= 32;
function getSingle($arr, $n)
{
global $INT_SIZE;
// Initialize result
$result = 0;
$x; $sum;
// Iterate through every bit
for ($i = 0; $i < $INT_SIZE; $i++)
{
// Find sum of set bits at ith
// position in all array elements
$sum = 0;
$x = (1 << $i);
for ($j = 0; $j < $n; $j++ )
{
if ($arr[$j] & $x)
$sum++;
}
// The bits with sum not multiple
// of 3, are the bits of element
// with single occurrence.
if (($sum % 3) !=0 )
$result |= $x;
}
return $result;
}
// Driver Code
$arr = array (12, 1, 12, 3, 12, 1,
1, 2, 3, 2, 2, 3, 7);
$n = sizeof($arr);
echo "The element with single occurrence is ",
getSingle($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find the element
// that occur only once
let INT_SIZE = 32;
function getSingle(arr, n)
{
// Initialize result
let result = 0;
let x, sum;
// Iterate through every bit
for (let i = 0; i < INT_SIZE; i++)
{
// Find sum of set bits at ith position in all
// array elements
sum = 0;
x = (1 << i);
for (let j = 0; j < n; j++)
{
if (arr[j] & x)
sum++;
}
// The bits with sum not multiple of 3, are the
// bits of element with single occurrence.
if ((sum % 3) != 0)
result |= x;
}
return result;
}
// Driver code
let arr = [ 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 ];
let n = arr.length;
document.write("The element with single occurrence is " + getSingle(arr, n));
// This code is contributed by mukesh07.
</script>
Producción
The element with single occurrence is 7
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Otro enfoque sugerido por Abhishek Sharma 44 . Suma cada número una vez y multiplica la suma por 3, obtendremos el triple de la suma de cada elemento del arreglo. Guárdelo como tres veces_sum. Resta la suma de toda la array de thrice_sum y divide el resultado por 2. El número que obtenemos es el número requerido (que aparece una vez en la array).
Array [] : [a, a, a, b, b, b, c, c, c, d]
Ecuación matemática = ( 3*(a+b+c+d) – (a + a + a + b + b + b + c + c + c + d) ) / 2
En palabras más sencillas: ( 3*(suma_de_array_sin_duplicados) – (suma_de_array) ) / 2
let arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Required no = ( 3*(sum_of_array_without_duplicates) - (sum_of_array) ) / 2
= ( 3*(12 + 1 + 3 + 2) - (12 + 1 + 12 + 3 + 12 + 1 + 1 + 2 + 3 + 3))/2
= ( 3* 18 - 50) / 2
= (54 - 50) / 2
= 2 (required answer)
Como sabemos, el conjunto no contiene ningún elemento duplicado,
pero std::set se implementa comúnmente como un árbol de búsqueda binario rojo-negro. La inserción en esta estructura de datos tiene una complejidad O(log(n)) en el peor de los casos, ya que el árbol se mantiene equilibrado. usaremos set aquí.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the element
// that occur only once
#include <bits/stdc++.h>
using namespace std;
// function which find number
int singleNumber(int a[], int n)
{
unordered_set<int> s(a, a + n);
int arr_sum = accumulate(a, a + n, 0); // sum of array
int set_sum = accumulate(s.begin(), s.end(), 0); // sum of set
// applying the formula.
return (3 * set_sum - arr_sum) / 2;
}
// driver function
int main()
{
int a[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 };
int n = sizeof(a) / sizeof(a[0]);
cout << "The element with single occurrence is " << singleNumber(a, n);
}
// This code is contributed by Mohit Kumar 29 (IIIT gwalior)
Java
// Java program to find the element
// that occur only once
import java.util.*;
class GFG {
// function which find number
static int singleNumber(int a[], int n)
{
HashSet<Integer> s = new HashSet<Integer>();
for (int i : a) {
s.add(i);
}
int arr_sum = 0; // sum of array
for (int i : a) {
arr_sum += i;
}
int set_sum = 0; // sum of set
for (int i : s) {
set_sum += i;
}
// applying the formula.
return (3 * set_sum - arr_sum) / 2;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 };
int n = a.length;
System.out.println("The element with single "
+ "occurrence is " + singleNumber(a, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the element
# that occur only once
# function which find number
def singleNumber(nums):
# applying the formula.
return (3 * sum(set(nums)) - sum(nums)) / 2
# driver function.
a = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
print ("The element with single occurrence is ",
int(singleNumber(a)))
C#
// C# program to find the element
// that occur only once
using System;
using System.Collections.Generic;
class GFG {
// function which find number
static int singleNumber(int[] a, int n)
{
HashSet<int> s = new HashSet<int>();
foreach(int i in a)
{
s.Add(i);
}
int arr_sum = 0; // sum of array
foreach(int i in a)
{
arr_sum += i;
}
int set_sum = 0; // sum of set
foreach(int i in s)
{
set_sum += i;
}
// applying the formula.
return (3 * set_sum - arr_sum) / 2;
}
// Driver code
public static void Main(String[] args)
{
int[] a = { 12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 };
int n = a.Length;
Console.WriteLine("The element with single "
+ "occurrence is " + singleNumber(a, n));
}
}
// This code is contributed by PrinciRaj1992
PHP
<?php
// PHP program to find the element
// that occur only once
//function which find number
function singleNumber($a, $n)
{
$s = array();
for ($i = 0; $i < count($a); $i++)
array_push($s, $a[$i]);
$s = array_values(array_unique($s));
$arr_sum = 0; // sum of array
for ($i = 0; $i < count($a); $i++)
{
$arr_sum += $a[$i];
}
$set_sum = 0; // sum of set
for ($i = 0; $i < count($s); $i++)
{
$set_sum += $s[$i];
}
// applying the formula.
return (int)(((3 * $set_sum) -
$arr_sum) / 2);
}
// Driver code
$a = array(12, 1, 12, 3, 12, 1,
1, 2, 3, 2, 2, 3, 7);
$n = count($a);
print("The element with single occurrence is " .
singleNumber($a, $n));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find the element
// that occur only once
// function which find number
function singleNumber(a,n)
{
let s = new Set(a);
let arr_sum = 0; // sum of array
for(let i=0;i<a.length;i++)
{
arr_sum += a[i];
}
let set_sum = 0; // sum of set
for (let i of s)
{
set_sum +=i;
}
// applying the formula.
return Math.floor((3 * set_sum - arr_sum) / 2);
}
// Driver code
let arr=[12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7 ];
let n = arr.length;
document.write("The element with single "
+ "occurrence is " + singleNumber(arr, n));
// This code is contributed by unknown2108
</script>
Producción
The element with single occurrence is 7
Complejidad temporal: O(Nlog(N))
Espacio auxiliar: O(N)
Método #4: Uso de la función Contador()
- Calcule la frecuencia de la array usando la función Contador
- Recorra este diccionario de contadores y verifique si alguna clave tiene valor 1
- Si el valor de cualquier clave es 1 devuelve la clave
A continuación se muestra la implementación:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// function which find number
int singlenumber(int a[],int N)
{
// umap for finding frequency
unordered_map<int,int>fmap;
// traverse the array for frequency
for(int i = 0; i < N;i++)
{
fmap[a[i]]++;
}
// iterate over the map
for(auto it:fmap)
{
// check frequency whether it is one or not.
if(it.second == 1)
{
// return it as we got the answer
return it.first;
}
}
}
// Driver code
int main()
{
// given array
int a[]={12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
// size of the array
int N=sizeof(a)/sizeof(a[0]);
// printing the returned value
cout << singlenumber(a,N);
return 0;
}
// This Code is contributed by
// Murarishetty Santhosh Charan
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// function which find number
static int singlenumber(int a[],int N)
{
// umap for finding frequency
Map<Integer, Integer> fmap
= new HashMap<Integer, Integer>();
// traverse the array for frequency
for(int i = 0; i < N;i++)
{
if(!fmap.containsKey(a[i]))
fmap.put(a[i],0);
fmap.put(a[i],fmap.get(a[i])+1);
}
// iterate over the map
for(Map.Entry<Integer, Integer> me : fmap.entrySet())
{
// check frequency whether it is one or not.
if(me.getValue()==1)
{
// return it as we got the answer
return me.getKey();
}
}
return -1;
}
// Driver code
public static void main (String[] args) {
// given array
int a[]={12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
// size of the array
int N= a.length;
// printing the returned value
System.out.println("The element with single occurrence is "+singlenumber(a,N));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
from collections import Counter
# Python3 program to find the element
# that occur only once
# function which find number
def singleNumber(nums):
# storing the frequencies using Counter
freq = Counter(nums)
# traversing the Counter dictionary
for i in freq:
# check if any value is 1
if(freq[i] == 1):
return i
# driver function.
a = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7]
print("The element with single occurrence is ",
int(singleNumber(a)))
# This code is contributed by vikkycirus
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
public class GFG {
// function which find number
static void singlenumber(int[] a, int N)
{
// umap for finding frequency
Dictionary<int, int> fmap = new Dictionary<int, int>();
// traverse the array for frequency
for (int i = 0; i < N; i++)
{
if (fmap.ContainsKey(a[i]))
fmap[a[i]]++;
else
fmap.Add(a[i], 1);
}
// iterate over the map
foreach (int it in fmap.Keys.ToList())
{
// check frequency whether it is one or not.
if(fmap[it] == 1)
{
// return it as we got the answer
Console.Write("The element with single occurrence is " + it);
}
}
}
// Driver Code
public static void Main (string[] args) {
// given array
int[] arr = {12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7};
// size of the array
int n= arr.Length;
// printing the returned value
singlenumber(arr, n);
}
}
// This code is contributed by splevel62.
Javascript
<script>
// Javascript program for the above approach
// function which find number
function singlenumber(a,N)
{
// umap for finding frequency
let fmap=new Map();
// traverse the array for frequency
for(let i = 0; i < N;i++)
{
if(!fmap.has(a[i]))
fmap.set(a[i],0);
fmap.set(a[i],fmap.get(a[i])+1);
}
// iterate over the map
for(let [key, value] of fmap.entries())
{
// check frequency whether it is one or not.
if(value==1)
{
// return it as we got the answer
return key;
}
}
}
// Driver code
// given array
let a = [12, 1, 12, 3, 12, 1, 1, 2, 3, 2, 2, 3, 7];
// size of the array
let N = a.length;
// printing the returned value
document.write("The element with single occurrence is "+singlenumber(a,N));
// This code is contributed by rag2127
</script>
Producción
The element with single occurrence is 7
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método #5: Usando el método count().
Podemos encontrar la ocurrencia de elementos usando el método count(). Si el método count() devuelve 1, entonces el elemento tiene una sola aparición.
Python3
# Python3 code to find the element that
# appears once
arr = [3, 3, 2, 3]
for i in arr:
if(arr.count(i)==1):
x=i
break
print("The element with single occurrence is ",x)
Producción
The element with single occurrence is 2
Este artículo fue compilado por Sumit Jain y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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