LeetCode 3513: Number of Unique XOR Triplets I ·

Table of Contents

LeetCode Bi-Weekly Contest 154 - This article is part of a series.

Part 1: LeetCode 3512: Minimum Operations to Make Array Sum Divisible by K

Part 2: This Article

Meta Data
#

Difficulty: medium First Attempt: 2025-04-12

Total time: 20:00.00 (TLE)

Intuition
#

My initial idea was to use a triple for-loop (O(n^3)) to iterate through all possible combinations of nums, and store the XOR results in a set called seen. However, this approach would obviously result in a TLE (Time Limit Exceeded) due to the three nested loops.

Then, I attempted to apply Digit DP, thinking it could help reduce duplicate calculations. For example:

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

We don’t need to recalculate expressions like 3 XOR 3 if the result has already been cached using lru_cache.

However, the issue is that, unlike many classic Digit DP problems where the result space is relatively small, the set of possible XOR results in this problem is quite large. As a result, lru_cache suffers from a high cache miss rate, and the performance gain is minimal. Eventually, this still leads to TLE.

I believe the only feasible solution here involves bit manipulation, though I haven’t found a clear explanation or an optimal approach yet.

Approach
#

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        
        from functools import lru_cache

        n = len(nums)

        @lru_cache(None)
        def dfs(position, num_index, xor_result):
            if position == 3:
                return {xor_result}

            result = set()
            for idx in range(num_index, n):
                result.update(
                    dfs(
                        position + 1,
                        idx,
                        xor_result ^ nums[idx]
                    )
                )

            return result

        return len(dfs(0, 0, 0))