Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.
Examples :
Input : arr = {1, 2, 3, 2, 3, 1, 3}
Output : 3
Input : arr = {5, 7, 2, 7, 5, 2, 5}
Output : 5
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
PHP
<?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 ?> |
Output:
5
A Better Solution is to use Hashing. Use array elements as key and their counts as value. Create an empty hash table. One by one traverse the given array elements and store counts. Time complexity of this solution is O(n). But it requires extra space for hashing.
Program :
PHP
<?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 ?> |
Output:
5
Please refer complete article on Find the Number Occurring Odd Number of Times for more details!
Please Login to comment…
<!–
–>
Php Program to Rotate the matrix right by K times
Php Program to Rearrange array such that arr[i] >= arr[j] if i is even and arr[i]<=arr[j] if i is odd and j < i
Php Program for Frequencies of even and odd numbers in a matrix
PHP Program for Find the number of islands | Set 1 (Using DFS)
Php Program to Find element at given index after a number of rotations
Php Program to Find the smallest missing number
Php Program to Find closest number in array
PHP Program for Program to cyclically rotate an array by one
PHP Program for Find the element that appears once
PHP Program to Find the closest pair from two sorted arrays
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
–>
… [Trackback]
[…] Read More here on that Topic: geeksforgeeks.org/php-program-to-find-the-number-occurring-odd-number-of-times-2/ […]