12

This is an interview question.

Given an array of integers, find the single integer value in the array which occurs with even frequency. All integers will be positive. All other numbers occur odd frequency. The max number in the array can be INT_MAX.

For example, [2, 8, 6, 2] should return 2.

the original array can be modified if you can find better solutions such as O(1) space with O(n) time.

I know how to solve it by hashtable (traverse and count freq). It is O(n) time and space.

Is it possible to solve it by O(1) space or better time?

Community
  • 1
  • 1
user1002288
  • 4,860
  • 10
  • 50
  • 78
  • 3
    You can't do better than inspecting every element at least once (on average), so you're not going to beat O(n) time. – Oliver Charlesworth Jan 18 '12 at 00:42
  • 2
    You don't even have to count the actual frequencies, just the frequencies modulo 2. ;) – Daniel Kamil Kozar Jan 18 '12 at 00:44
  • 1
    Is there a target to beat or is this a "what's the best you can do" question? – Jon Jan 18 '12 at 00:44
  • The target O(1) space is fixed and achievable, the target "better time" is best you can do. – Eugen Rieck Jan 18 '12 at 00:54
  • "It is O(n) time and space." Hash tables are *NOT* O(n) time! (Worst case complexity O(n^2). If you implement it differently O(nlog(n)) – ElKamina Jan 18 '12 at 01:18
  • @ElKamina- Hash tables are *expected* O(n) time, and the probability that it runs in any worse can be shown to be exponentially small using the appropriate type of hash table. – templatetypedef Jan 18 '12 at 02:35
  • 1
    Are you allowed to modify the original array? Is there a bound on the numbers? – templatetypedef Jan 18 '12 at 02:36
  • 3
    Possible duplicate of http://stackoverflow.com/questions/7292965/finding-a-number-that-repeats-even-no-of-times-where-all-the-other-numbers-repea and http://stackoverflow.com/questions/8022454/finding-even-number-of-times-repeating-integer-in-an-array-where-rest-of-the-int – Timothy Jones Jan 18 '12 at 03:57
  • Hmm... A radix sort can be used to find the even occuring integer. Assuming one integer has to occur at least twice, the number of buckets would be O(n-1) which would be O(1), right? – Justin Jan 18 '12 at 18:50
  • Justin, O(n-1) is still O(n). – Emil Vikström Oct 06 '12 at 09:16

5 Answers5

6

Given this is an interview question, the answer is: O(1) space is achievable "for very big values of 1":

  • Prepare a matcharray 1..INT_MAX of all 0
  • When traversing the array, use the integer as an index into the matcharray, adding 1
  • When done, traverse the match array to find the one entry with a positive even value

The space for this is large, but independent of the size of the input array, so O(1) space. For really big data sets (say small value range, but enormous array length), this might even be a practically valid solution.

Eugen Rieck
  • 64,175
  • 10
  • 70
  • 92
4

If you are allowed to sort the original array, I believe that you can do this in O(n lg U) time and O(lg U) space, where U is the maximum element of the array. The idea is as follows - using in-place MSD radix sort, sort the array in O(n lg U) time and O(lg U) space. Then, iterate across the array. Since all equal values are consecutive, you can then count how many times each value appears. Once you find the value that appears an even number of times, you can output the answer. This second scan requires O(n) time and O(1) space.

If we assume that U is a fixed constant, this gives an O(n)-time, O(1)-space algorithm. If you don't assume this, then the memory usage is still better than the O(n) algorithm provided that lg U = O(n), which should be true on most machines. Moreover, the space usage is only logarithmically as large as the largest element, meaning that the practical space usage is quite good. For example, on a 64-bit machine, we'd need only space sufficient to hold 64 recursive calls. This is much better than allocating a gigantic array up-front. Moreover, it means that the algorithm is a weakly-polynomial time algorithm as a function of U.

That said, this does rearrange the original array, and thus does destructively modify the input. In a sense, it's cheating because it uses the array itself for the O(n) storage space.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
1

Scan through the list maintaining two sets, the 'Even' set and the 'Odd' set. If an element hasn't been seen before (i.e. if it's in neither set), place it in the 'Odd' set. If an element is in one set, move it to the other set. At the end, there should be only one item in the 'Even' set. This probably won't be fast, but the memory usage should be reasonable for large lists.

Aaron McDaid
  • 26,501
  • 9
  • 66
  • 88
  • Can you boil this down to big-O time and space complexity? – Oliver Charlesworth Jan 18 '12 at 01:48
  • 1
    This is O(n) time, O(n) space. – templatetypedef Jan 18 '12 at 02:34
  • 1
    If it's O(n) time, that implies that a single item can be scanned on O(1), which implies that the sets can be checked and items swapped over in O(1). But I don't see how that would work. How can you check if a given number is in a set in O(1)? If we knew the range of the numbers (all numbers will be less than 100, for example), then we could use an array of that length to achieve that. But I don't see how we can deal with arbitrarily large numbers in O(1), it would require some sort of hash set. Are we allowed to use a lot of memory to give us sparsely populated hashes which are O(1)? – Aaron McDaid Jan 18 '12 at 12:06
0

-Make a hash table containing ints. Call it is_odd or something. Since you might have to look through an array of size INT_MAX, just make it an array of size INT_MAX. Initialize to 0.

-Traverse through the whole array. You have to do this. There's no way to beat O(n).

for each number:
  if it's not in the hash table, mark its spot in the table as 1.

  if it is in the hash table then:
    if its value is '1', make it '2'
    if its value is '2', make it '1'.

Now you have to traverse through the hash table. Pull out the sole entry with "2" as the value.

Time: You traverse the array once and the hash table once, so O(n).

Space: Just an array of size INT_MAX. Or if you know the range of your array you can restrict your memory use to that.

edit: I just saw that you already had this method. Sorry about that!

AlexQueue
  • 6,353
  • 5
  • 35
  • 44
-2

I guess we read the task improperly. It asks us "find the single integer value in the array which occurs with even frequency". So, assuming that there is exactly ONE even element, the solution is:

public static void main(String[] args) {
    int[] array = { 2, 1, 2, 4, 4 };

    int count = 0;
    for (int i : array) {
        count^=i;
    }
    System.out.println(count); // Prints 1
}
Dmitry Kalashnikov
  • 2,021
  • 1
  • 12
  • 3