Our job is to find the element with odd occurrence in O(n) time complexity and O(1) Auxiliary space.
The solution is to do bitwise XOR. XOR (^) of all elements gives us odd occurring element.
#include<bits/stdc++.h>
using namespace std;
void findOddOccuring(int arr[], int size){
int x=0; // Initializing with zero.
for(int i=0;i<size;i++){
x^=arr[i];
}
printf("The number appearing odd times is
%d\n",x);
//3 occurs odd number of times.Feel
free to change
// elements in the array.
}
#include<bits/stdc++.h>
using namespace std;
int main(){
int arr[]={1,2,1,3,4,4,2};
int size = sizeof(arr)/sizeof(arr[0]);
findOddOccuring(arr,size);
return 0;}
No comments:
Post a Comment