🔐 Q3. Number of Unique XOR Triplets II – Explained with Optimized C++ Solution

Are you preparing for coding interviews or contests and stumbled upon "Number of Unique XOR Triplets II"? You're in the right place. In this blog post, we’ll dive deep into this fascinating problem from LeetCode, understand what it asks, explore the logic step-by-step, and finally implement an efficient solution in C++ using Dynamic Programming (DP) and bitwise XOR.

Let’s get started!

🧠 Problem Statement

You are given a list of integers nums. Your task is to find how many distinct XOR values you can get from all triplets (i, j, k) such that:

i < j < k, and
XOR of nums[i], nums[j], and nums[k] is taken.

Additionally, triplets like (i, i, i) are valid if the number occurs at least once. So, both 3-element combinations and single elements (used as triplet) are considered.

💡 Understanding XOR

Before diving into the solution, let’s understand XOR ( ^ ):

a ^ a = 0
a ^ 0 = a
XOR is commutative and associative
Often used to find differences, toggles, and combinations in bits

🧩 Key Observations

We're interested in all unique values of the XOR of triplets.
Any value in nums can itself be a valid triplet like (i, i, i).
We must consider all 3-element combinations (without repetition) whose XOR we haven’t seen before.

⚙️ Optimal Strategy (Dynamic Programming)

Why not brute force?

Brute-forcing all possible triplets would take O(n³) time. With n ≤ 10⁵ in some cases, it’s impractical.

Dynamic Programming Insight

Let’s define a DP state:

dp[k][t] = true if there exists a combination of `k` elements whose XOR is `t`

Where:

k ranges from 0 to 3
t ranges from 0 to 2048 (since max XOR with 11 bits is 2048)

This approach avoids repetition and computes all possible XOR combinations efficiently.

🔧 Step-by-Step C++ Implementation

class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        const int MAXX = 2048; // Max XOR value (2^11)
        int n = nums.size();

        // Step 1: Remove duplicates
        unordered_set<int> set;
        for (int x : nums) {
            set.insert(x);
        }
        vector<int> uniqueNums(set.begin(), set.end());

        // Step 2: Initialize DP table
        bool dp[4][MAXX] = {};
        dp[0][0] = true;

        // Step 3: Fill the DP table
        for (int x : uniqueNums) {
            for (int k = 2; k >= 0; --k) {
                for (int t = 0; t < MAXX; ++t) {
                    if (dp[k][t]) {
                        dp[k + 1][t ^ x] = true;
                    }
                }
            }
        }

        // Step 4: Collect all valid XORs
        unordered_set<int> res;
        for (int x : nums) {
            res.insert(x); // for (i, i, i)
        }

        for (int t = 0; t < MAXX; ++t) {
            if (dp[3][t]) {
                res.insert(t);
            }
        }

        return res.size();
    }
};

🧪 Dry Run Example

Input:

nums = {1, 2, 3}

Step-by-step triplets:

XOR(1, 1, 1) = 1 ✅
XOR(2, 2, 2) = 2 ✅
XOR(3, 3, 3) = 3 ✅
XOR(1, 2, 3) = 0 ✅

Result: {0, 1, 2, 3} → Output = 4

⏱️ Time and Space Complexity

Time Complexity: O(n × MAXX × k) = O(n × 2048 × 3) = ~O(n)
Space Complexity: O(3 × 2048) = O(6144)

Very efficient even for large n.

📌 Final Thoughts

The "Number of Unique XOR Triplets II" is a great mix of bit manipulation, set theory, and dynamic programming. By converting the brute-force triple-loop into a DP table that tracks XOR states, we drastically improve performance.

🔥 Key Takeaways:

Use unordered_set to remove duplicates and track results.
Traverse k backwards to avoid overwriting DP states.
Initialize dp[0][0] = true as a base case for XOR accumulation.

🗣️ Let’s Discuss

Still confused about the dynamic programming transition or how XOR is used here? Drop a comment or reach out on Code Se Career – YouTube or Instagram!

📎 Tags:

XOR problems, Dynamic Programming, LeetCode Solutions, Bit Manipulation, C++ Interview Questions, Unique Triplets, DP XOR, C++ DP Problems, Competitive Programming

AlgoPush

Search This Blog