PHP Challenges: Find majority element in an array

Last update on December 20 2024 10:22:25 (UTC/GMT +8 hours)

Write a PHP program to find majority element in an array.

Input : array(1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6)

Note: The majority element is the element that appears more than n/2 times where n is the number of elements in the array.

Explanation :

PHP: Find majority element in an array

Sample Solution :

PHP Code :

<?php
// Function to find the majority element in an array
function majority_element($arr)
{
    // Initialize index and counter variables
    $idx = 0;
    $ctr = 1;

    // Iterate through the array starting from index 1
    for ($i = 1; $i < sizeof($arr); $i++)
    {
        // If the current element is the same as the element at the current index
        if ($arr[$idx] == $arr[$i])
        {
            // Increment the counter
            $ctr += 1;
        }
        else
        {
            // Decrement the counter
            $ctr -= 1;

            // If the counter becomes 0, update the index to the current index and reset the counter to 1
            if ($ctr == 0)
            {
                $idx = $i;
                $ctr = 1;
            }
        }
    }

    // Return the majority element found at the index
    return $arr[$idx];
}

// Test arrays
$num1 = array(1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6);
$num2 = array(1, 2, 3, 3, 3, 3, 2, 3, 5, 3, 1, 3, 3, 4, 6, 1, 3, 3, 4, 6, 6);

// Test the majority_element function with the test arrays and print the results
print_r(majority_element($num1) . "\n");
print_r(majority_element($num2) . "\n");
?>

Explanation:

Here is a brief explanation of the above PHP code:

Function definition (majority_element):

The function "majority_element()" takes an array '$arr' as input.
It initializes two variables: '$idx' to track the index of the potential majority element, and '$ctr' to count the occurrences of the potential majority element.

Inside the function:

The function iterates through the array starting at index 1.
For each element, it checks if it matches the element at the current index ('$idx').
If the element matches, it increments the counter '$ctr'.
If the element doesn't match, it decrements the counter '$ctr'. If '$ctr' becomes 0, it updates '$idx' to the current index and resets '$ctr' to 1.
After iterating through the array, the element at index '$idx' is returned as the majority element.

Function Call & Testing:

The "majority_element()" function is tested with two different arrays ('$num1' and '$num2').
Finally, the "print_r()" function prints the majority element found in each array.

Sample Output:

5                                                           
3

Flowchart:

PHP Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a PHP program to push all zeros to the end of an array.
Next: Write a PHP program to find the length of the last word in a string.