Coding Exercise – C++ – Single Number II – Online Judge


Remember a couple days ago, we discussed the O(n) and O(n^2) solutions to Single Number ?

Question: Given an array of integers, every element appears three times except for one. Find that single one (appear only once).

Note:
Your algorithm should have a linear runtime complexity. Try to implement it without using extra memory

This problem is from [here].

This problem is quite similar to this one except each element appears three times (not twice). If appeared twice, we can use XOR to cancel out elements that appear twice and leave only the single one.

tex_8fb1f5024a605dc7737c61a8a376e067 Coding Exercise - C++ - Single Number II - Online Judge algorithms bit hacks brute force c / c++ code implementation math programming languages solution

We have tex_8fb1f5024a605dc7737c61a8a376e067 Coding Exercise - C++ - Single Number II - Online Judge algorithms bit hacks brute force c / c++ code implementation math programming languages solution similarly for this problem with little modification. First, we need to find out a non-used integer as a flag. And we mark elements checked one by one until we find a single one. The checked elements will be skipped to avoid time exceeded.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int singleNumber(int A[], int n) {
        /* find the min */
        int min = A[0];
        for (int i = 1; i < n; i ++) {
            if (A[i] < min) {
                min = A[i];
            }
        }
        / * find the non-used flag */
        int kmin = min + 1;
        do {
            int flag = 0;
            for (int i = 0; i < n; i ++) {
                if (A[i] == kmin) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) break;
            kmin ++;
        } while (true);
        for (int i = 0; i < n; i ++) {
            if (A[i] == kmin) continue; // skip checked-elements
            int c = 0;
            int k = A[i];
            A[i] = kmin;
            for (int j = i + 1; j < n; j ++) { // check for duplicate
                if (A[j] == k) {
                    c ++;
                    A[j] = kmin;   // mark checked
                    if (c == 2) break;
                }
            }
            if (c != 2) return k; // find it
        }
    }
};
class Solution {
public:
    int singleNumber(int A[], int n) {
        /* find the min */
        int min = A[0];
        for (int i = 1; i < n; i ++) {
            if (A[i] < min) {
                min = A[i];
            }
        }
        / * find the non-used flag */
        int kmin = min + 1;
        do {
            int flag = 0;
            for (int i = 0; i < n; i ++) {
                if (A[i] == kmin) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) break;
            kmin ++;
        } while (true);
        for (int i = 0; i < n; i ++) {
            if (A[i] == kmin) continue; // skip checked-elements
            int c = 0;
            int k = A[i];
            A[i] = kmin;
            for (int j = i + 1; j < n; j ++) { // check for duplicate
                if (A[j] == k) {
                    c ++;
                    A[j] = kmin;   // mark checked
                    if (c == 2) break;
                }
            }
            if (c != 2) return k; // find it
        }
    }
};

This gives a AC! in 284ms, way too slow!.

tex_caa5d58969fcc95bcd6477b6782501fa Coding Exercise - C++ - Single Number II - Online Judge algorithms bit hacks brute force c / c++ code implementation math programming languages solution

We notice in the problem description that the single number only appear once. Therefore, if you first represent the numbers in binary bits, and sum up each bit accordingly. The result modules 3 will be zero for all other elements, the remainder will be the bit value for that single number.

Wow, this looks simple and effective, just check each bit, sum it and do the modules by three, sum up the remainder (the OR).

All look nice by using bit-shifting.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNumber(int A[], int n) {
        int count[32] = {0};
        int result = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++) {                 
                if ((A[j] >> i) & 1) {
                    count[i]++; // sum up the bits
                }
            }
            result |= ((count[i] % 3) << i); // restore
        }
        return result;
    }
};
class Solution {
public:
    int singleNumber(int A[], int n) {
        int count[32] = {0};
        int result = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++) {                 
                if ((A[j] >> i) & 1) {
                    count[i]++; // sum up the bits
                }
            }
            result |= ((count[i] % 3) << i); // restore
        }
        return result;
    }
};

This gives a AC! in 64ms, a lot faster even it is strictly speaking, a tex_caa5d58969fcc95bcd6477b6782501fa Coding Exercise - C++ - Single Number II - Online Judge algorithms bit hacks brute force c / c++ code implementation math programming languages solution!

The Fastest tex_caa5d58969fcc95bcd6477b6782501fa Coding Exercise - C++ - Single Number II - Online Judge algorithms bit hacks brute force c / c++ code implementation math programming languages solution, Yeah!

Wonder the fastest solution? It is based on the above bit idea. We will have three bitmasks values (ones, twos, threes) to represent bits had appeared once, twice and three times.

For any element that appears three times, clear the bitmasks for ones and twos, the final value will be ones.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0, twos = 0, xthrees = 0;
        for(int i = 0; i < n; i++){
            twos |= ones & A[i];
            ones =  ones ^ A[i]; 
            xthrees = ~(ones & twos); // not threes
            ones = ones & xthrees; // clear 
            twos = twos & xthrees; // clear
        }
        return ones;
    }
};
class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0, twos = 0, xthrees = 0;
        for(int i = 0; i < n; i++){
            twos |= ones & A[i];
            ones =  ones ^ A[i]; 
            xthrees = ~(ones & twos); // not threes
            ones = ones & xthrees; // clear 
            twos = twos & xthrees; // clear
        }
        return ones;
    }
};

This gives a AC! in 52ms, the fastest solution!

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
832 words
Last Post: Tutorial 5 - C Programming in 6502 - Video RAM
Next Post: Tutorial 6 - C Programming in 6502 - Reading Joysticks

The Permanent URL is: Coding Exercise – C++ – Single Number II – Online Judge

Leave a Reply