CareerCup

Do an XOR operation on all the numbers.. final output is the number which appears odd number of times.

xor all the elements.. the result will be the element which appear odd no. of times.

1. Sort the array
2. read through the sorted array and find the integer that appears odd number of times
Complexity = O(n log n) + O(n)

take one more array of size equal to domain of the integers present in the given array

initialise this array with zero(count)
trevel to the original array increase the corresponding count value in new array..and finally travel this new array to know the output i.e. count value should be odd

Apply xor operation on given array elements and result is the required element

we can think on soritng and hashing also

soln1.) O(2n)=O(n)
1.)Push the count of elements in the HASHMAP - O(n)
2.)loop through the elements in the hashmap and check for %2==0 if not then thts the integer O(n)

soln2.) Solution requires O(n), does not require u to loop thru the hashmap entries
1.)Push/increments the count element in the hashmap
2.)Decrement the count as you see the element again when tranversing
and keep a check if the count is 0 if yes, delete the hashmap entry
3.)The last element remaining in the hashmap is the element required

ya. good .. nice approach

we can solve the problem with the help of hashmap or hashtable aswell.
1 read through the area and keep the elements and its count in hashmap
2 the value is already available . increase the count value .
3 if it is not available . put entry in hashmap element with the count value 1
finally iterate through hashmap and check for entry for which odd number of count value.

so time complexity-o(n)
space complexity-o(n)

we can solve the problem with the help of hashmap or hashtable aswell.
1 read through the area and keep the elements and its count in hashmap
2 the value is already available . increase the count value .
3 if it is not available . put entry in hashmap element with the count value 1
finally iterate through hashmap and check for entry for which odd number of count value.

so time complexity-o(n)
space complexity-o(n)
Reply to Comment

Java Pseudocode
int[] arrContent={1,3,7,3,9,7,1};
// Papulate hash map content
HashMap<int,int> oddMap=new<int,int> HashMap();
for(int i=0;i<arrContent.length;i++) {
if(!oddMap.containKey(arrContent[i])) {
oddMap.put(arrContent[i],1);
}
else {
int count=oddMap.get(arrContent[i]);
oddMap.put(arrContent[i],++count);
}
}

// iterate through hashmap and find the value

Set set=oddMap.keySet();
Iterator it=set.iterator();
while(it.hasnext()) {
int element=it.next();
int countVal=oddMap.get(element)
if(countVal%2==1) {
System.out.println(" Element with the odd number of count"+element);
}
}

Java Pseudocode
int[] arrContent={1,3,7,3,9,7,1};
// Papulate hash map content
HashMap<int,int> oddMap=new<int,int> HashMap();
for(int i=0;i<arrContent.length;i++) {
if(!oddMap.containKey(arrContent[i])) {
oddMap.put(arrContent[i],1);
}
else {
int count=oddMap.get(arrContent[i]);
oddMap.put(arrContent[i],++count);
}
}

// iterate through hashmap and find the value

Set set=oddMap.keySet();
Iterator it=set.iterator();
while(it.hasnext()) {
int element=it.next();
int countVal=oddMap.get(element)
if(countVal%2==1) {
System.out.println(" Element with the odd number of count"+element);
}
}

sorry i forgot to put break statement within if block

#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int n;
int a[100],count[100]={0};
cout<<"enter no of elements";
cin>>n;
cout<<"enter the elements";
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
count[a[i]]++;
for(int i=0;i<n;i++)
{
if((count[a[i]]%2)!=0)
{cout<<"element repeating odd tyms is "<<a[i];break;}
}
getch();
}

|x|y|xor|
|0|0| 0 |
|0|1| 1 |
|1|0| 1 |
|1|1| 0 |

x^0=x
x^1=!x
x^x=0

from the above truth table and equations we can see that any number x which is xor'd with itself an even number of times will result in zero.  However, if it is xor'd with itself an odd number of times then the result will be itself.

for example:
int numbers[] = { 1,2,1 };
int result = 0;

result ^= numbers[0] = 1;
result ^= numbers[1] = 3;
result ^= numbers[2] = 2;

The best approach to solve the above algorithm is to xor all the array elements by themselves and then the element which is repeated the odd number of times will be the final output.