Ex-or the numbers. For the odd occurrence, the ex-oring will not result in zero.

View Allnum of num

Software Engineer Interview Seattle, WA

Amazon## Given a (potentially large) array of integers, all but one

repeating an even number of times, how would you find the one repeating an odd number of times in an efficient way? eg [1 2 3 3 2 2 1 4 2] should return 4

Tags:

data structures, analytical See More, See Less8

7 Answers

▲

7

▼

Ex-or the numbers. For the odd occurrence, the ex-oring will not result in zero.

▲

0

▼

Ex-oring is a great idea, one other solution is to sort the array and then in one pass you can find out the number that occurs odd number of time

with quicksort avg case nlogn and worst case n^2

▲

1

▼

Few steps of counting sort can help us do it in O(n) time.

Step I: find min and max, thus the range

Step 2: initialize array of the range with 0

Step3: as numbers come in, increment the a[number] by 1.

Step4: scan the array to find the odd number.

▲

1

▼

Ex-or is a good solution only if 0 is not in the input list. If 0 occurs odd number of times, not sure it will report it.

▲

0

▼

Tellig about zero is an excellent catch.. +1

▲

0

▼

by using LINQ it can be acheived.

var numList = new List() {1 ,2, 3, 3, 2, 2, 1, 4, 2 };

var oneOccurance = numList.GroupBy(x => x).Where(y => y.Count() == 1).Select(y => y.Key); //Ans = {4}

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

Use any collection data structure to insert and remove the numbers, such that at the end the only one remaining will be the one repeated an odd number of times.

For example we can use a tree. We consider on number at the time. We first search for the number in the tree. If found, we will remove it. Otherwise, we will insert it. At the end, the number (or the numbers, in general) repeated an odd number of times will be in the tree. For the complexity it is necessary to perform an amortized analysis.

Another data structure that we can use is the hashmap. However, the space consumption and management could be high, if the map automatically resizes.