CareerCup

<pre lang="" line="1" title="CodeMonkey85273" class="run-this">public class FindTheGuyAppearingEvenTimes {

public static int find(int[] arr) {
Set<Integer> set = new HashSet<Integer>();

// Due to HashSet's nature, the set will contain every number once after
// the loop
for (int i : arr) {
set.add(i);
}

// Check all numbers, if a number exists in the set already, remove it,
// otherwise add it to the set
for (int i : arr) {
if (set.contains(i)) {
set.remove(i);
} else {
set.add(i);
}
}

// Now the set contains only one number, which appears even times
return set.toArray(new Integer[0])[0];
}

public static void main(String[] args) {
int[] arr = { 5, 5, 5, 6, 6, 9, 9, 9, 9, 9, 123, 250, 560, 720, 720,
720 };
System.out.println(find(arr));
}
}
</pre><pre title="CodeMonkey85273" input="yes">
</pre>

can we use hashmap?Store the integers as keys and number of times it occurs as values.and get the key whose value %2 == 0.
time complexity will be o(n) for put and o(1) for get.

IF the question is like this that all number are even time and one is odd time..
It will become very easy...;)
just take XOR

yes. But this is in other way.
I have suggested binary tree , where , if node is missing , will add node in that position. If element is there , will remove that element.

So at the end , the tree contains all elements , except the even count number.

Once tree is built , we will check for the missing element .

But I think complexity for missing element is O(nlogn) .. (please correct me if complexity is wrong)

Is the range of the integers given?

should be binary SEARCH tree i think…

I gave O(nlogn) algo , but the person is expecting o(n) complexity algo.

<pre lang="" line="1" title="CodeMonkey50645" class="run-this">Actually the code above can be improved by using xor after first loop.

public class FindOnlyEvenAppearanceAmongOddOnse {

public static int findTheGuyAppearingEvenTimes(int[] arr) {
Set<Integer> set = new HashSet<Integer>();

// Due to HashSet's nature, the set will contain every number once after the loop
for (int i : arr) {
set.add(i);
}

int ret = 0;
for (int i : set.toArray(new Integer[0])) {
ret ^= i;
}
for (int i : arr) {
ret ^= i;
}

return ret;
}

public static void main(String[] args) {
int[] arr = { 5, 5, 5, 9, 9, 9, 9, 9, 123, 250, 560, 720, 250, 720, 720 };
System.out.println(findTheGuyAppearingEvenTimes(arr));
}
}</pre><pre title="CodeMonkey50645" input="yes">
</pre>

1. OR all the numbers
2. XOR all the numbers
3. XOR the result of 1 and 2 you will get the answer

e.g 2,5,5

2 = 010
5 = 101
5 = 101

OR all of them = 010|101|101 = 111 = R1
XOR all of them = 010^101^101 = 010 = R2
XOR R1 , R2 = 111^010 = 101 = 5 which occurs even number of times.

XORing a number even times result in 0 and 0 XOR any number is equal to original number.
But, note that XOR can not distinguish 1 ^ 2 from 3
ie. arr = [ 1, 2, 3, 5, 5, 6]

OR = 7
XOR = 6
OR ^ XOR = 1 <= wrong answer.

what if we maintain 2 lookups? but we need to know the maxi number in the array.. or use realloc to increase the sizes of these array dynamically.

lookup1 - puts a 1 against the number when it appears once.. if it appears again then puts 0
lookup2 - turns on(1) when the number changes from 1-0(even) in lookup1 and viceversa when 0-1.

so ultimately when we are traversing the array and updating these lookups O(n).. and lookup2 will have only one entry which will have 1 in it.. so go thru each element in the array and check for this 1.. Therefore O(2n) = O(n)

but the space complexity issue arises if the numbers are large.. the lookups will increase..

what if we maintain 2 lookups? but we need to know the maxi number in the array.. or use realloc to increase the sizes of these array dynamically.

lookup1 - puts a 1 against the number when it appears once.. if it appears again then puts 0
lookup2 - turns on(1) when the number changes from 1-0(even) in lookup1 and viceversa when 0-1.

so ultimately when we are traversing the array and updating these lookups O(n).. and lookup2 will have only one entry which will have 1 in it.. so go thru each element in the array and check for this 1.. Therefore O(2n) = O(n)

but the space complexity issue arises if the numbers are large.. the lookups will increase..

consider array 1 2 2 3 4 3 4 4 3
algorithm
int a[4]={-1}//all elements
for i=0 to end of array
if(a[array[i]]<0)a[array[i]++ //add if odd
else a[array[i]-- //sub if even

now which ever element in array "a" has -1 as its value is the number which is repeated even time.. time complexity is O(n)

1) Get binary equivalent of the number.
2) all odd number have 1 at end , even number have 0.
3) Check if the number has 0 in end. That's the number.
e.g 8 -> 1000.

{}

Well, can we make it a little bit more complicated: if there are more than one numbers repeated even numbers of time. Then how to print those?

(1) xor all the elements and say the result of xor be in 'ans' variable.
i.e
int ans = 0;
for(int i = 0; i < n; i++)
{
ans = ans ^ a[i];
}

(2) Then xor ans with each element seperately and check if the value of ans changes. If it doesn't change then that is the corresponding number i.e

for(int i = 0; i < n; i++)
{
if( ans ^ a[i] == ans )
return a[i];
}