Frontend School

Distinct Subsequence XOR Sums

DSA
medium

Distinct Subsequence XOR Sums

Medium
Bit Manipulation
Arrays
Linear Algebra

Overview

In financial data analysis, identifying unique patterns or combinations from a set of values can reveal underlying structures. Consider a scenario where an array of non-negative integers represents various market indicators. We are interested in understanding the diversity of "XOR signatures" that can be formed by combining any subset of these indicators. This problem challenges you to determine the total count of unique XOR sums achievable from all possible non-empty subsequences of a given array. This requires an efficient application of bitwise properties to identify linearly independent combinations.

What you need to do / Task

  1. Implement a function countDistinctXorSums(nums) that takes an array of non-negative integers.
  2. The function should return the total number of distinct XOR sums that can be formed by taking any non-empty subsequence of nums.

Input & output

  • nums: An array of non-negative integers (number[] in TypeScript/JavaScript).
  • Returns: A single integer (number) representing the count of distinct XOR sums.

Clarifications

  • An empty subsequence is not considered for forming XOR sums. However, if 0 can be formed by a non-empty subsequence (e.g., [5, 5] or [3, 5, 6] from Example 1), it should be counted as one of the distinct sums.
  • The order of elements in a subsequence does not affect its XOR sum.
  • nums can contain duplicate elements. Each instance contributes to forming subsequences.

Examples

1

Example 1

Input:

nums = [3, 5, 6]

Output:

4

Note:

The numbers are: 3 (011_2), 5 (101_2), 6 (110_2). A basis for these numbers can be {3, 5}. The distinct XOR sums are {0, 3, 5, 6}. There are 4 distinct sums, which is 2^(basis size 2).

2

Example 2

Input:

nums = [7, 7, 7]

Output:

2

Note:

The number is 7 (111_2). A basis for these numbers can be {7}. The distinct XOR sums are {0, 7}. There are 2 distinct sums, which is 2^(basis size 1).

3

Example 3

Input:

nums = [0, 1, 2]

Output:

4

Note:

The numbers are: 0 (000_2), 1 (001_2), 2 (010_2). A basis for these numbers can be {1, 2}. Note that 0 does not contribute to increasing the basis size. The distinct XOR sums are {0, 1, 2, 3}. There are 4 distinct sums, which is 2^(basis size 2).

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < 2^20 (all numbers fit within a 20-bit integer)
  • The maximum number of bits (max_bits) for any number will not exceed 20.

Out of scope

  • Handling numbers larger than 2^20 — assume standard integer types are sufficient.
  • Optimizing for scenarios where nums.length is extremely small and max_bits is extremely large, or vice versa (the current approach is balanced).

What interviewers evaluate

  • Correct implementation of the bitwise Gaussian elimination (XOR basis) algorithm.
  • Optimal time complexity (e.g., O(N * max_bits)) and space complexity (e.g., O(max_bits)).
  • Ability to correctly handle the implications of 0 being a possible XOR sum from non-empty subsequences.
  • Code clarity, maintainability, and proper use of bitwise operators.

Loading editor...