PHP Challenges: Find a single element in an array where every element appears three times except for one

PHP Challenges - 1: Exercise-10 with Solution

Write a PHP program to find a single element in an array where every element appears three times except for one.

Input : array(5, 3, 4, 3, 5, 5, 3)

Explanation :

Sample Solution :

PHP Code :

<?php
// Function to find the single number in an array using bitwise operations
function single_number($arr)
{
    // Initialize variables for storing ones, twos, and common bits between ones and twos
    $ones = 0;
    $twos = 0;
    $common_one_two = 0;

    // Iterate through the array
    for ($i = 0; $i < sizeof($arr); $i++)
    {
        // Update twos using bitwise OR and bitwise AND operations
        $twos  = $twos | ($ones & $arr[$i]);

        // Update ones using bitwise XOR operation
        $ones  = $ones ^ $arr[$i];

        // Calculate common bits between ones and twos
        $common_one_two = ~($ones & $twos);

        // Remove common bits from ones and twos
        $ones &= $common_one_two;
        $twos &= $common_one_two;
    }

    // Return the single number found
    return $ones;
}

// Define two arrays
$arr1 = array(5, 3, 4, 3, 5, 5, 3);
$arr2 = array(-1, 1, 1, -1, -1, 1, 0);

// Print the first array
print_r($arr1);
// Print the single number found in the first array
print_r('Single Number: ' . single_number($arr1) . "\n");

// Print the second array
print_r($arr2);
// Print the single number found in the second array
print_r('Single Number: ' . single_number($arr2) . "\n");
?>

Explanation:

Here is a brief explanation of the above PHP code:

• Function definition:
• The code defines a function named "single_number()" which finds the single number in an array using bitwise operations. It takes an array '$arr' as input.
• Inside the function:
• It initializes three variables '$ones', '$twos', and '$common_one_two' to 0.
• It iterates through the array using a "for" loop.
• Within each iteration, it updates '$twos' using bitwise OR and bitwise AND operations, updates '$ones' using bitwise XOR operation, and calculates common bits between '$ones' and '$twos'.
• It then removes the common bits from '$ones' and '$twos'.
• After the loop, it returns the single number found, which is stored in '$ones'.
• Function Call & Testing:
• Two arrays '$arr1' and '$arr2' are defined with different sets of numbers.
• The "single_number()" function is called twice with these arrays as input.
• The input arrays and single numbers are printed using "print_r()".

Sample Output:

Array                                                       
(                                                           
    [0] => 5                                                
    [1] => 3                                                
    [2] => 4                                                
    [3] => 3                                                
    [4] => 5                                                
    [5] => 5                                                
    [6] => 3                                                
)                                                           
Single Number: 4                                            
Array                                                       
(                                                           
    [0] => -1                                               
    [1] => 1                                                
    [2] => 1                                                
    [3] => -1                                               
    [4] => -1 
	[5] => 1                                                
    [6] => 0                                                
)                                                           
Single Number: 0    

Flowchart:

PHP Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a PHP program to find a single number in an array that doesn't occur twice.
Next: Write a PHP program to find the single element appears once in an array where every element appears twice except for one.