Friday, April 10, 2015

LeetCode OJ - Single Number II

Problem:

Please find the problem here.

Solution:

We already solved Single Number, so all we have to do is to generalize it. Considering exclusive-or as addition modulo 2, all we really need is addition modulo 3, and do that per digit.

So the first step is to extend the number into a base 3 number instead of base 2. As binary representation, we will need one more bit per bit, so I used an 64-bit integer, the most significant 32 bits are the most significant bit for the digit. So it is represented like this:

Base 3 representation: 2 0 1 0
Binary representation 10 00 01 00
Represented in code: 1 0 0 0 0 0 1 0

The cool thing about this representation is that we can change a number into its base 3 version simply by adding a bunch of 0 before it, and obviously, we can extract the original number by just taking the lowest 32 bits.

So we simply extract each digit, add it, modulo 3, and put it back, nothing special about that.

Last but not least, if somehow the array has 3n + 2 elements, we need to divide the number by 2. It can be easily done by multiplying it with the multiplicative inverse of 2, which is 2 again because (2 x 2 = 4 = 1 mod 3).

Be careful with signed integer, we need to explicitly cast it to unsigned to avoid sign extension.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/single-number-ii/

#include "LEET_SINGLE_NUMBER_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SINGLE_NUMBER_II
{
    typedef long long int64;

    class Solution
    {
    public:
        int singleNumber(int A[], int n)
        {
            int64 accumulator = 0;
            for (int i = 0; i < n; i++)
            {
                int64 lo_mask = 1;
                int64 hi_mask = (int64)1 << 32;
                for (int d = 0; d < 32; d++)
                {
                    int64 ac_lo = accumulator & lo_mask;
                    int64 ac_hi = accumulator & hi_mask;
                    int64 ar_lo = (unsigned int)A[i] & lo_mask;
                    int64 ar_hi = (unsigned int)A[i] & hi_mask;

                    int ac_digit = ((ac_hi == 0) ? 0 : 2) + ((ac_lo == 0) ? 0 : 1);
                    int ar_digit = ((ar_hi == 0) ? 0 : 2) + ((ar_lo == 0) ? 0 : 1);

                    int sum = (ac_digit + ar_digit) % 3;

                    accumulator = accumulator & ~lo_mask;
                    accumulator = accumulator & ~hi_mask;

                    switch (sum)
                    {
                    case 0:
                        // The digit is already reset
                        break;
                    case 1:
                        accumulator = accumulator | lo_mask;
                        break;
                    case 2:
                        accumulator = accumulator | hi_mask;
                        break;
                    }

                    lo_mask = lo_mask << 1;
                    hi_mask = hi_mask << 1;
                }
            }

            if (n % 3 == 2)
            {
                int64 lo_mask = 1;
                int64 hi_mask = (int64)1 << 32;
                for (int d = 0; d < 32; d++)
                {
                    int64 ac_lo = accumulator & lo_mask;
                    int64 ac_hi = accumulator & hi_mask;

                    int ac_digit = ((ac_hi == 0) ? 0 : 2) + ((ac_lo == 0) ? 0 : 1);

                    int quoient = (ac_digit * 2) % 3;

                    accumulator = accumulator & ~lo_mask;
                    accumulator = accumulator & ~hi_mask;
                    accumulator = accumulator & ~lo_mask;
                    accumulator = accumulator & ~hi_mask;

                    switch (quoient)
                    {
                    case 0:
                        // The digit is already reset
                        break;
                    case 1:
                        accumulator = accumulator | lo_mask;
                        break;
                    case 2:
                        accumulator = accumulator | hi_mask;
                        break;
                    }

                    lo_mask = lo_mask << 1;
                    hi_mask = hi_mask << 1;
                }
            }

            return (accumulator << 32) >> 32;
        }
    };
};

using namespace _LEET_SINGLE_NUMBER_II;

int LEET_SINGLE_NUMBER_II()
{
    int A[] = { -2, -2, 1, 1, -3, 1, -3, -3, -4, -2 };
    Solution solution;
    cout << solution.singleNumber(A, 10) << endl;
    return 0;
}

1 comment :

  1. Here is another solution
    public class Solution {
    public int singleNumber(int[] nums) {
    int p = 0;
    int q = 0;
    for(int i = 0; i<nums.length; i++){
    p = q & (p ^ nums[i]);
    q = p | (q ^ nums[i]);
    }
    return q;
    }
    }
    Analysis from this blog post : http://traceformula.blogspot.com/2015/08/single-number-ii-how-to-come-up-with.html 

    ReplyDelete