Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space.
Examples :
Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Output: 2
In the given array all element appear three times except 2 which appears once.Input: arr[] = {10, 20, 10, 30, 10, 30, 30}
Output: 20
In the given array all element appear three times except 20 which appears once.
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
PHP
<?php function getSingle($arr, $n) { $ones = 0; $twos = 0 ; $common_bit_mask; // Let us take the example of // {3, 3, 2, 3} to understand this for($i = 0; $i < $n; $i++ ) { /* The expression "one & arr[i]" gives the bits that are there in both \'ones\' and new element from arr[]. We add these bits to \'twos\' using bitwise OR Value of \'twos\' will be set as 0, 3, 3 and 1 after 1st, 2nd, 3rd and 4th iterations respectively */ $twos = $twos | ($ones & $arr[$i]); /* XOR the new bits with previous \'ones\' to get all bits appearing odd number of times Value of \'ones\' will be set as 3, 0, 2 and 3 after 1st, 2nd, 3rd and 4th iterations respectively */ $ones = $ones ^ $arr[$i]; /* The common bits are those bits which appear third time. So these bits should not be there in both \'ones\' and \'twos\'. common_bit_mask contains all these bits as 0, so that the bits can be removed from \'ones\' and \'twos\' Value of \'common_bit_mask\' will be set as 00, 00, 01 and 10 after 1st, 2nd, 3rd and 4th iterations respectively */ $common_bit_mask = ~($ones & $twos); /* Remove common bits (the bits that appear third time) from \'ones\' Value of \'ones\' will be set as 3, 0, 0 and 2 after 1st, 2nd, 3rd and 4th iterations respectively */ $ones &= $common_bit_mask; /* Remove common bits (the bits that appear third time) from \'twos\' Value of \'twos\' will be set as 0, 3, 1 and 0 after 1st, 2nd, 3rd and 4th itearations respectively */ $twos &= $common_bit_mask; // uncomment this code to see // intermediate values // printf (" %d %d n", ones, twos); } return $ones; } // Driver Code $arr = array(3, 3, 2, 3); $n = sizeof($arr); echo "The element with single " . "occurrence is ", getSingle($arr, $n); // This code is contributed by m_kit ?> |
Please refer complete article on Find the element that appears once for more details!
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
<!–
–>
Php Program to Find element at given index after a number of rotations
Php Program to Find a triplet such that sum of two equals to third element
Php Program to Find lost element from a duplicated array
Php Program to Find maximum element of each row in a matrix
Php Program To Find Next Greater Element
Php Program for Third largest element in an array of distinct elements
Php Program for Last duplicate element in a sorted array
Php Program for Search an element in a sorted and rotated array
PHP Program for Program to cyclically rotate an array by one
PHP Program to Find the Number Occurring Odd Number of Times
Article Contributed By :
neveropen
Vote for difficulty
Article Tags :
Report Issue
<!–
Please write us at contribute@geeksforgeeks.org to report any issue with the above content
–>
Please Login to comment…