## Amazon Interview Question

Software Engineer / Developers- 0of 0 votes
An array of integers, only one integer appears odd times, all others appear even times, find it

XOR of a number with itself will give you a 0. 0 XOR'd with any number will give you the same number. Thus an even count of a particular number will give you a 0 while an odd count will give you the number itself.

If you XOR all values one after the other, the even count values will cancel each other out and only the odd count value will remain at the end.

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

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

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);

}

}

#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;
```

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

- Teja February 02, 2010