The best way to find the single number in pairs or triples

Question

As this is one question in a series of questions. I am modifying this to make it not duplicate from other ones. Thanks for all the help.

Pairs: I have an array of integers. In the array, every element appears twice except for one. I want to find that single number.

Example: [2, 4, 2, 1, 4, 1, 3], single number is 3.

My thought is to use a HashMap, which takes O(n) time and O(n) space. Are there any better solutions? Thanks.

Triples: every element appears three times except for one. Find that single one.

Example: [1, 2, 4, 2, 4, 1, 2, 4, 1, 3], single number is 3.

Is the array somehow orderd, such that the elements that are twice appear always in pairs like in your example. or is an array like [1,2,3,1,2] allowed, to? — AlexWien, Jan 20 '16 at 18:17
Possible duplicate of [Accenture interview question - find the only unpaired element in the array](http://stackoverflow.com/questions/2644179/accenture-interview-question-find-the-only-unpaired-element-in-the-array) — RiaD, Jan 20 '16 at 18:20
http://stackoverflow.com/q/29333689/768110 http://stackoverflow.com/q/35185/768110 — RiaD, Jan 20 '16 at 18:21
@RiaD Hi, thanks for pointing that out. I have modified the question. Please check again. — , Jan 20 '16 at 18:27
@RiaD It is still to find the single number. I will add some more explanations. Maybe Panda has a solution for the new problem as well. — , Jan 20 '16 at 18:28

score 6 · Accepted Answer · 2016-01-20T18:33:04.973

6

Think about solving it in the "bit" way, which takes O(n) time and O(1) space:

public class Solution {
    public int singleNumber(int[] A) {
        if (A.length==0) return 0;
        if (A.length==1) return A[0];

        int result = A[0];

        for (int i=1; i<A.length; i++) {
            result = result ^ A[i];
        }

        return result;         
    }
}

Well, yes, I also have the solution for finding the single one in triples.

public class Solution {
    public int singleNumber(int[] A) {
        int result = 0;

        for (int i = 0; i < 32; i++) {
            int curr = 0;
            for (int num : A) {
                curr += (num >> i) & 1;
            }
            result += (curr % 3) << i;
        }

        return result;
    }
}

This can be more difficult for you to understand. Please read some materials about bit manipulation and then figure out how this solution works.

edited Jan 20 '16 at 18:33

answered Jan 20 '16 at 18:17

Interesting, Is that from "Hackers Delight" – AlexWien Jan 20 '16 at 18:19
Thanks for your prompt reply. What is "^"? – Jan 20 '16 at 18:19
@AlexWien Just solved this problem before. I was even shocked when I saw this bit manipulation solution. – Jan 20 '16 at 18:21
@Noob, about ^ (xor) http://stackoverflow.com/questions/1991380/what-does-the-operator-do-in-java – Igor Tyulkanov Jan 20 '16 at 18:21
@Learner Thanks. I will google and get to know more about this. – Jan 20 '16 at 18:21
@IgorTyulkanov Thank you. – Jan 20 '16 at 18:22
@Noob if you solved it with the hashmap, that would be the normal solution. The trick with xor, one has to know. The book "Hackers Delight " shows such tricks with bit manipulation,. – AlexWien Jan 20 '16 at 18:24
Hi, do you have a solution for the new edited question by any chance? Thanks in advance! – Jan 20 '16 at 18:30
@AlexWien I did not read "Hackers Delight". I got the solutions from other websites when I was preparing for some interviews. – Jan 20 '16 at 18:35
@Panda Thank you so much! – Jan 20 '16 at 18:36
Intersting, which company needs such bit tricks, maybe Nvidia, but who else? – AlexWien Jan 20 '16 at 18:38
@AlexWien I was preparing for Google onsite interviews. Just in case, it was better to know about bit manipulations. – Jan 20 '16 at 18:41

The best way to find the single number in pairs or triples

1 Answers1