Dado um array de inteiros positivos. Todos os números ocorrem número par de vezes, exceto um número que ocorre número ímpar de vezes. Encontre o número em tempo O (n) e espaço constante.

Exemplos :

Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3

Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5

<?php
// PHP program to find the 
// element occurring odd
// number of times
  
// Function to find the element 
// occurring odd number of times
function getOddOccurrence(&$arr, $arr_size)
{
    $count = 0;
    for ($i = 0; 
         $i < $arr_size; $i++) 
    {
          
        for ($j = 0;
             $j < $arr_size; $j++)
        {
            if ($arr[$i] == $arr[$j])
                $count++;
        }
        if ($count % 2 != 0)
            return $arr[$i];
    }
    return -1;
}
  
// Driver code
$arr = array(2, 3, 5, 4, 5, 2, 
             4, 3, 5, 2, 4, 4, 2);
$n = sizeof($arr);
  
// Function calling
echo(getOddOccurrence($arr, $n));
  
// This code is contributed
// by Shivi_Aggarwal
?>

<?php
// PHP program to find the 
// element occurring odd 
// number of times
  
// Function to find element 
// occurring odd number of times
function getOddOccurrence(&$ar, $ar_size)
{
    $res = 0; 
    for ($i = 0; $i < $ar_size; $i++)     
        $res = $res ^ $ar[$i];
      
    return $res;
}
  
// Driver Code
$ar = array(2, 3, 5, 4, 5, 2,
            4, 3, 5, 2, 4, 4, 2);
$n = sizeof($ar);
  
// Function calling
echo(getOddOccurrence($ar, $n));
      
// This code is contributed 
// by Shivi_Aggarwal
?>

Artigo contribuído por:

GeeksforGeeks

Vote na dificuldade

<button class="btn" data-gfg-action="article-difficulty" data-rating="1">Fácil</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="2">Normal</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="3">Médio</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="4">Duro</button> <button class="btn" data-gfg-action="article-difficulty" data-rating="5">Especialista</button>

Tags de artigo:

• Programas PHP

Reportar problema