Dada una array donde todos los elementos aparecen un número par de veces excepto dos, imprima los dos elementos impares. Se puede suponer que el tamaño de la array es al menos dos.
Ejemplos: 30
Input : arr[] = {2, 3, 8, 4, 4, 3, 7, 8}
Output : 2 7
Input : arr[] = {15, 10, 10, 50 7, 5, 5, 50, 50, 50, 50, 50}
Output : 7 15
Solución simple :
Acercarse :
Una solución simple es usar dos bucles anidados. El bucle exterior atraviesa todos los elementos. El bucle interno cuenta las ocurrencias del elemento actual. Imprimimos los elementos cuyos recuentos de ocurrencias son impares.
A continuación se muestra el código del enfoque dado:
C++
// CPP code to find two odd occurring elements
// in an array where all other elements appear
// even number of times.
#include <bits/stdc++.h>
using namespace std;
void printOdds(int arr[], int n)
{
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j]) {
count += 1;
}
}
if (count % 2 != 0) {
cout << arr[i]
<< " "; // Print the elements that occur
// odd number of times in an array
}
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 3, 4, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// function call
printOdds(arr, n);
return 0;
}
// This code is contributed by Suruchi Kumari
C
// C code to find two odd occurring elements
// in an array where all other elements appear
// even number of times.
#include <stdio.h>
void printOdds(int arr[], int n)
{
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (arr[i] == arr[j]) {
count += 1;
}
}
if (count % 2 != 0) {
printf(
"%d ",
arr[i]); // Print the elements that occur
// odd number of times in an array
}
}
printf("\n");
}
// Driver code
int main()
{
int arr[] = { 2, 3, 3, 4, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// function call
printOdds(arr, n);
return 0;
}
// This code is contributed by Suruchi Kumari
Python3
# python3 code for the above approach # Function to find and Replace in String def printOdds(arr, n) : for i in range(0,n) : count = 0 for j in range(0,n) : if arr[i] == arr[j] : count += 1 if count % 2 != 0 : print(arr[i],end=' ') # Print the elements that occur # odd number of times in an array # Driver code if __name__ == "__main__" : arr = [ 2, 3, 3, 4, 4, 5 ] n = len(arr) #Function call printOdds(arr,n) # This code is contributed by adityapatil12
Javascript
// JavaScript code to find two odd occurring elements
// in an array where all other elements appear
// even number of times.
function printOdds(arr, n)
{
for (var i = 0; i < n; i++) {
let count = 0;
for (var j = 0; j < n; j++) {
if (arr[i] == arr[j]) {
count += 1;
}
}
if (count % 2 != 0) {
process.stdout.write(arr[i] + " ");
// Print the elements that occur
// odd number of times in an array
}
}
process.stdout.write("\n");
}
// Driver code
let arr = [ 2, 3, 3, 4, 4, 5 ];
let n = arr.length;
// function call
printOdds(arr, n);
// This code is contributed by phasing17
Producción
2 5
Complejidad del tiempo: O(n^2)
Espacio auxiliar : O(n)
Una mejor solución es usar hashing. La complejidad temporal de esta solución es O(n) pero requiere espacio extra.
Podemos construir un mapa hash de frecuencia, luego iterar sobre todos sus pares clave-valor e imprimir todas las claves cuyos valores (frecuencia) son impares.
C++
// CPP code to find two odd occurring elements
// in an array where all other elements appear
// even number of times.
#include <bits/stdc++.h>
using namespace std;
void printOdds(int arr[], int n)
{
//declaring an unordered map
unordered_map<int, int> freq;
//building the frequency table
for (int i = 0; i < n; i++)
freq[arr[i]]++;
//iterating over the map
for (auto& it: freq) {
//if the frequency is odd
//print the element
if (it.second % 2)
cout << it.first << " ";
}
}
// Driver code
int main()
{
int arr[] = { 2, 3, 3, 4, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
//function call
printOdds(arr, n);
return 0;
}
//this code is contributed by phasing17
Producción
5 2
Complejidad de tiempo: O(n)
Complejidad espacial: O(n)
Una solución eficiente es utilizar operadores bit a bit. La idea se basa en el enfoque utilizado en dos elementos que faltan y dos elementos que se repiten .
C++
// CPP code to find two odd occurring elements
// in an array where all other elements appear
// even number of times.
#include <bits/stdc++.h>
using namespace std;
void printOdds(int arr[], int n)
{
// Find XOR of all numbers
int res = 0;
for (int i = 0; i < n; i++)
res = res ^ arr[i];
// Find a set bit in the XOR (We find
// rightmost set bit here)
int set_bit = res & (~(res - 1));
// Traverse through all numbers and
// divide them in two groups
// (i) Having set bit set at same
// position as the only set bit
// in set_bit
// (ii) Having 0 bit at same position
// as the only set bit in set_bit
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (arr[i] & set_bit)
x = x ^ arr[i];
else
y = y ^ arr[i];
}
// XOR of two different sets are our
// required numbers.
cout << x << " " << y;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 3, 4, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
printOdds(arr, n);
return 0;
}
Java
// Java code to find two
// odd occurring elements
// in an array where all
// other elements appear
// even number of times.
class GFG
{
static void printOdds(int arr[],
int n)
{
// Find XOR of
// all numbers
int res = 0;
for (int i = 0; i < n; i++)
res = res ^ arr[i];
// Find a set bit in the
// XOR (We find rightmost
// set bit here)
int set_bit = res &
(~(res - 1));
// Traverse through all
// numbers and divide them
// in two groups (i) Having
// set bit set at same position
// as the only set bit in
// set_bit (ii) Having 0 bit at
// same position as the only
// set bit in set_bit
int x = 0, y = 0;
for (int i = 0; i < n; i++)
{
if ((arr[i] & set_bit) != 0)
x = x ^ arr[i];
else
y = y ^ arr[i];
}
// XOR of two different
// sets are our required
// numbers.
System.out.println( x + " " + y);
}
// Driver code
public static void main(String [] args)
{
int arr[] = { 2, 3, 3,
4, 4, 5 };
int n = arr.length;
printOdds(arr, n);
}
}
// This code is contributed by
// Smitha Dinesh Semwal
Python3
# Python 3 code to find two # odd occurring elements in # an array where all other # elements appear even number # of times. def printOdds(arr, n): # Find XOR of all numbers res = 0 for i in range(0, n): res = res ^ arr[i] # Find a set bit in # the XOR (We find # rightmost set bit here) set_bit = res & (~(res - 1)) # Traverse through all numbers # and divide them in two groups # (i) Having set bit set at # same position as the only set # bit in set_bit # (ii) Having 0 bit at same # position as the only set # bit in set_bit x = 0 y = 0 for i in range(0, n): if (arr[i] & set_bit): x = x ^ arr[i] else: y = y ^ arr[i] # XOR of two different # sets are our # required numbers. print(x , y, end = "") # Driver code arr = [2, 3, 3, 4, 4, 5 ] n = len(arr) printOdds(arr, n) # This code is contributed # by Smitha
C#
// C# code to find two
// odd occurring elements
// in an array where all
// other elements appear
// even number of times.
using System;
class GFG
{
static void printOdds(int []arr,
int n)
{
// Find XOR of
// all numbers
int res = 0;
for (int i = 0; i < n; i++)
res = res ^ arr[i];
// Find a set bit in the
// XOR (We find rightmost
// set bit here)
int set_bit = res &
(~(res - 1));
// Traverse through all
// numbers and divide them
// in two groups (i) Having
// set bit set at same position
// as the only set bit in
// set_bit (ii) Having 0 bit at
// same position as the only
// set bit in set_bit
int x = 0, y = 0;
for (int i = 0; i < n; i++)
{
if ((arr[i] & set_bit) != 0)
x = x ^ arr[i];
else
y = y ^ arr[i];
}
// XOR of two different
// sets are our required
// numbers.
Console.WriteLine(x + " " + y);
}
// Driver code
public static void Main()
{
int []arr = { 2, 3, 3,
4, 4, 5 };
int n = arr.Length;
printOdds(arr, n);
}
}
// This code is contributed by
// Akanksha Rai(Abby_akku)
PHP
<?php
// PHP code to find two odd
// occurring elements in an
// array where all other elements
// appear even number of times.
function printOdds($arr, $n)
{
// Find XOR of all numbers
$res = 0;
for ($i = 0; $i < $n; $i++)
$res = $res ^ $arr[$i];
// Find a set bit in the
// XOR (We find rightmost
// set bit here)
$set_bit = $res & (~($res - 1));
// Traverse through all numbers
// and divide them in two groups
// (i) Having set bit set at same
// position as the only set bit
// in set_bit
// (ii) Having 0 bit at same position
// as the only set bit in set_bit
$x = 0;
$y = 0;
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] & $set_bit)
$x = $x ^ $arr[$i];
else
$y = $y ^ $arr[$i];
}
// XOR of two different sets
// are our required numbers.
echo($x . " " . $y);
}
// Driver code
$arr = array( 2, 3, 3, 4, 4, 5 );
$n = sizeof($arr);
printOdds($arr, $n);
// This code is contributed by Smitha
?>
Javascript
<script>
// Javascript code to find two odd
// occurring elements in an array
// where all other elements appear
// even number of times.
function printOdds(arr, n)
{
// Find XOR of all numbers
let res = 0;
for(let i = 0; i < n; i++)
res = res ^ arr[i];
// Find a set bit in the XOR (We find
// rightmost set bit here)
let set_bit = res & (~(res - 1));
// Traverse through all numbers and
// divide them in two groups
// (i) Having set bit set at same
// position as the only set bit
// in set_bit
// (ii) Having 0 bit at same position
// as the only set bit in set_bit
let x = 0, y = 0;
for(let i = 0; i < n; i++)
{
if (arr[i] & set_bit)
x = x ^ arr[i];
else
y = y ^ arr[i];
}
// XOR of two different sets are our
// required numbers.
document.write(x + " " + y);
}
// Driver code
let arr = [ 2, 3, 3, 4, 4, 5 ];
let n = arr.length;
printOdds(arr, n);
// This code is contributed by subhammahato348
</script>
Producción
5 2
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)