XOR-like solution O(n) time and O(1) space in C++


  • 2
    T

    As you can solve Single number with :

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int r = 0;
            for(int i : nums)
                r ^= i;
            return r;
        }
    };
    

    You can invent a commutative operation on (0, 1, 2), in your ternary represention, such as x * x * x = 0:

      0 1 2
    0 0 1 2
    1 1 2 0
    2 2 0 1
    

    This gives:

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            long long r = 0;
            for(int j : nums)
            {
                long long i = j + (1LL << 32);
                long long x = r, p = 1;
                r = 0;
                while(i || x)
                {
                    r += p*(((i%3)+(x%3))%3);
                    i /= 3;
                    x /= 3;
                    p *= 3;
                }
            }
            return r - (1LL << 32);
        }
    };
    

    We add 2^32 for an easy gestion of negative numbers.
    The operation is coded as (a + b) % 3.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.