In an array having positive integers, except for one number which occurs odd number of times, all other numbers occur even number of times. Find the number. Example - Input : 2 5 9 1 5 1 8 2 8 Output: 9
Input : 2 3 4 3 1 4 5 1 4 2 5 Output: 4
Please try solving this problem before jumping on the solution
Click to learn
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
Algorithm 1: Count the occurrence of each array element and check if it is odd or not. Print the element which has odd occurrence. This algorithm uses two loops and runs in O(n2) time.
Algorithm 2: Create a hash map to store the element as key and count of the element as value. Iterate over the array elements. If the array element is not present in the array, then add the element to the map with count = 1. If the array element is already present because of a previous iteration, then update the count of the array by incrementing the count by 1. Finally iterate over the map and print the element which has odd occurrence. This algorithm takes O(n) time and O(n) auxiliary space.
Algorithm 3: 1. Initialize result = input. 2. Iterate over the array from i = 1 to length of the array and XOR the result with each element of the input array. 3. Once iteration over the array is done, print result as the output.
XOR operation Truth Table -
Truth Table of A XOR B shows that it outputs true whenever the input differs.
XOR operation of a number with itself results in 0. Example: Consider 5 XOR 5 Binary representation for 5 is 101. Hence applying bitwise XOR on 5 following rules given in the above truth table - 101 XOR 101 = 000 = 0 Now, if XOR is applied on the above result with 5, we get 5 XOR 5 XOR 5 as - 000 XOR 101 = 101 = 5
XOR operation on a number with itself even number of times will result in 0. XOR operation on a number with itself odd number of times will result in the number itself. This algorithm takes O(n) time and O(1) auxiliary space.
Code for all the above algorithms is given in Code Snippet section.
Support us by whitelisting IDeserve in your ad-blocker.