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.
solution
We have 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!.
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 solution!
The Fastest 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) —
loading...
Last Post: Tutorial 5 - C Programming in 6502 - Video RAM
Next Post: Tutorial 6 - C Programming in 6502 - Reading Joysticks