Dada una array de enteros. Todos los números ocurren dos veces excepto un número que ocurre una vez. Encuentre el número en tiempo O(n) y espacio extra constante.
Ejemplo :
C++
// C++ program to find the array element that appears only
// once
#include <iostream>
using namespace std;
int findSingle(int ar[], int ar_size)
{
// Do XOR of all elements and return
int res = ar[0];
for (int i = 1; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
// Driver code
int main()
{
int ar[] = { 2, 3, 5, 4, 5, 3, 4 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "Element occurring once is "
<< findSingle(ar, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find the array element that appears only
// once
#include <stdio.h>
int findSingle(int ar[], int ar_size)
{
// Do XOR of all elements and return
int res = ar[0];
for (int i = 1; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
// Driver code
int main()
{
int ar[] = { 2, 3, 5, 4, 5, 3, 4 };
int n = sizeof(ar) / sizeof(ar[0]);
printf("Element occurring once is %d",
findSingle(ar, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find the array
// element that appears only once
class MaxSum
{
// Return the maximum Sum of difference
// between consecutive elements.
static int findSingle(int ar[], int ar_size)
{
// Do XOR of all elements and return
int res = ar[0];
for (int i = 1; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
// Driver code
public static void main (String[] args)
{
int ar[] = {2, 3, 5, 4, 5, 3, 4};
int n = ar.length;
System.out.println("Element occurring once is " +
findSingle(ar, n) + " ");
}
}
// This code is contributed by Prakriti Gupta
Python3
# function to find the once # appearing element in array def findSingle( ar, n): res = ar[0] # Do XOR of all elements and return for i in range(1,n): res = res ^ ar[i] return res # Driver code ar = [2, 3, 5, 4, 5, 3, 4] print "Element occurring once is", findSingle(ar, len(ar)) # This code is contributed by __Devesh Agrawal__
C#
// C# program to find the array
// element that appears only once
using System;
class GFG
{
// Return the maximum Sum of difference
// between consecutive elements.
static int findSingle(int []ar, int ar_size)
{
// Do XOR of all elements and return
int res = ar[0];
for (int i = 1; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
// Driver code
public static void Main ()
{
int []ar = {2, 3, 5, 4, 5, 3, 4};
int n = ar.Length;
Console.Write("Element occurring once is " +
findSingle(ar, n) + " ");
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find the array
// element that appears only once
function findSingle($ar, $ar_size)
{
// Do XOR of all
// elements and return
$res = $ar[0];
for ($i = 1; $i < $ar_size; $i++)
$res = $res ^ $ar[$i];
return $res;
}
// Driver code
$ar = array(2, 3, 5, 4, 5, 3, 4);
$n = count($ar);
echo "Element occurring once is "
, findSingle($ar, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find the array
// element that appears only once
function findSingle(ar, ar_size)
{
// Do XOR of all elements and return
let res = ar[0];
for (let i = 1; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
// Driver code
let ar = [2, 3, 5, 4, 5, 3, 4];
let n = ar.length;
document.write("Element occurring once is "
+ findSingle(ar, n));
// This code is contributed by Surbhi Tyagi
</script>
C++
// C++ program to find
// element that appears once
#include <bits/stdc++.h>
using namespace std;
// function which find number
int singleNumber(int nums[],int n)
{
map<int,int> m;
long sum1 = 0,sum2 = 0;
for(int i = 0; i < n; i++)
{
if(m[nums[i]] == 0)
{
sum1 += nums[i];
m[nums[i]]++;
}
sum2 += nums[i];
}
// applying the formula.
return 2 * (sum1) - sum2;
}
// Driver code
int main()
{
int a[] = {2, 3, 5, 4, 5, 3, 4};
int n = 7;
cout << singleNumber(a,n) << "\n";
int b[] = {15, 18, 16, 18, 16, 15, 89};
cout << singleNumber(b,n);
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program to find
// element that appears once
import java.io.*;
import java.util.*;
class GFG
{
// function which find number
static int singleNumber(int[] nums, int n)
{
HashMap<Integer, Integer> m = new HashMap<>();
long sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i++)
{
if (!m.containsKey(nums[i]))
{
sum1 += nums[i];
m.put(nums[i], 1);
}
sum2 += nums[i];
}
// applying the formula.
return (int)(2 * (sum1) - sum2);
}
// Driver code
public static void main(String args[])
{
int[] a = {2, 3, 5, 4, 5, 3, 4};
int n = 7;
System.out.println(singleNumber(a,n));
int[] b = {15, 18, 16, 18, 16, 15, 89};
System.out.println(singleNumber(b,n));
}
}
// This code is contributed by rachana soma
Python3
# Python3 program to find # element that appears once # function which find number def singleNumber(nums): # applying the formula. return 2 * sum(set(nums)) - sum(nums) # driver code a = [2, 3, 5, 4, 5, 3, 4] print (int(singleNumber(a))) a = [15, 18, 16, 18, 16, 15, 89] print (int(singleNumber(a))) # This code is contributed by "Abhishek Sharma 44"
C#
// C# program to find
// element that appears once
using System;
using System.Collections.Generic;
class GFG
{
// function which find number
static int singleNumber(int[] nums, int n)
{
Dictionary<int,int> m = new Dictionary<int,int>();
long sum1 = 0, sum2 = 0;
for (int i = 0; i < n; i++)
{
if (!m.ContainsKey(nums[i]))
{
sum1 += nums[i];
m.Add(nums[i], 1);
}
sum2 += nums[i];
}
// applying the formula.
return (int)(2 * (sum1) - sum2);
}
// Driver code
public static void Main(String []args)
{
int[] a = {2, 3, 5, 4, 5, 3, 4};
int n = 7;
Console.WriteLine(singleNumber(a,n));
int[] b = {15, 18, 16, 18, 16, 15, 89};
Console.WriteLine(singleNumber(b,n));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find
// element that appears once
// function which find number
function singleNumber(nums,n)
{
let m = new Map();
let sum1 = 0, sum2 = 0;
for (let i = 0; i < n; i++)
{
if (!m.has(nums[i]))
{
sum1 += nums[i];
m.set(nums[i], 1);
}
sum2 += nums[i];
}
// applying the formula.
return (2 * (sum1) - sum2);
}
// Driver code
let a=[2, 3, 5, 4, 5, 3, 4];
let n = 7;
document.write(singleNumber(a,n)+"<br>");
let b=[15, 18, 16, 18, 16, 15, 89];
document.write(singleNumber(b,n));
// This code is contributed by unknown2108
</script>
C++
#include <bits/stdc++.h>
using namespace std;
int singleelement(int arr[], int n)
{
int low = 0, high = n - 2;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == arr[mid ^ 1])
low = mid + 1;
else
high = mid - 1;
}
return arr[low];
}
int main()
{
int arr[] = { 2, 3, 5, 4, 5, 3, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + size);
cout << singleelement(arr, size);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
#include <stdio.h>
#include<stdlib.h>
// Compare function for qsort
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
int singleelement(int arr[], int n)
{
int low = 0, high = n - 2;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == arr[mid ^ 1])
low = mid + 1;
else
high = mid - 1;
}
return arr[low];
}
int main()
{
int arr[] = { 2, 3, 5, 4, 5, 3, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
qsort(arr, size, sizeof(int), cmpfunc);
printf("%d", singleelement(arr, size));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
import java.io.*;
import java.util.Arrays;
class GFG{
static int singleelement(int arr[], int n)
{
int low = 0, high = n - 2;
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if (arr[mid] == arr[mid ^ 1])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return arr[low];
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 5, 4, 5, 3, 4 };
int size = 7;
Arrays.sort(arr);
System.out.println(singleelement(arr, size));
}
}
// This code is contributed by dassohom5
Python3
def singleelement(arr, n): low = 0 high = n - 2 mid = 0 while (low <= high): mid = (low + high) // 2 if (arr[mid] == arr[mid ^ 1]): low = mid + 1 else: high = mid - 1 return arr[low] # Driver code arr = [2, 3, 5, 4, 5, 3, 4] size = len(arr) arr.sort() print(singleelement(arr, size)) # This code is contributed by shivanisingh
C#
using System;
using System.Collections;
class GFG{
static int singleelement(int[] arr, int n)
{
int low = 0, high = n - 2;
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if (arr[mid] == arr[mid ^ 1])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return arr[low];
}
// Driver code
public static void Main()
{
int[] arr = { 2, 3, 5, 4, 5, 3, 4 };
int size = 7;
Array.Sort(arr);
Console.WriteLine(singleelement(arr, size));
}
}
// This code is contributed by dassohom5
Javascript
<script>
function singleelement(arr,n)
{
let low = 0, high = n - 1;
let mid;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == arr[mid ^ 1]) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return arr[low];
}
let arr = [ 2, 3, 5, 4, 5, 3, 4 ];
let size = arr.length;
arr = arr.sort(function(a,b){return a-b})
document.write(singleelement(arr, size));
</script>
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