Frontend School

Count of Distinct Subset XOR Sums

DSA
hard

Count of Distinct Subset XOR Sums

Hard
Bit Manipulation
Arrays
Linear Algebra

Overview

In fields like distributed systems, network routing, or cryptography, understanding the properties of bitwise operations is fundamental for tasks such as data integrity verification or generating unique identifiers. This problem focuses on the diversity of values achievable through XOR operations. Given a collection of numbers, your task is to determine how many distinct values can be formed by XORing elements from all possible non-empty subsets of that collection. This requires a deep understanding of bitwise algebra and efficient algorithmic techniques.

What you need to do / Task

Implement the function countDistinctXorSums that takes an array of non-negative integers nums and returns the total count of unique XOR sums that can be generated from its non-empty subsets.

Input & output

  • Input: nums: number[]
    • An array of non-negative integers.
  • Output: number
    • An integer representing the total count of distinct XOR sums. This count must include 0 if it is a possible XOR sum from a non-empty subset (e.g., x ^ x = 0).

Clarifications

  • An empty subset's XOR sum is 0. However, the problem explicitly states non-empty subsets. If 0 can be formed by XORing elements of a non-empty subset (e.g., [5, 5] yields 5^5 = 0), it should be included in the count.
  • The order of elements in a subset does not affect the XOR sum.
  • All numbers nums[i] are non-negative, implying operations on unsigned integers.

Examples

1

Example 1

Input:

nums = [1, 2, 3]

Output:

4

Note:

The numbers 1, 2, and 3 can form a basis. Specifically, 1 and 2 are linearly independent. 3 (binary 011) can be expressed as 1 ^ 2. Since 3 is linearly dependent on 1 and 2, it implies 0 can be formed by a non-empty subset (1 ^ 2 ^ 3 = 0). The unique XOR sums are {0, 1, 2, 3}, totaling 4 distinct values.

2

Example 2

Input:

nums = [5, 5, 10]

Output:

4

Note:

The number 5 (binary 0101) can be a basis element. The second 5 is linearly dependent (5 ^ 5 = 0), indicating 0 can be formed by a non-empty subset. 10 (binary 1010) is linearly independent of 5. The basis has two elements (e.g., 5 and 10), spanning {0, 5, 10, 15}. There are 4 distinct XOR sums.

3

Example 3

Input:

nums = [7]

Output:

1

Note:

Only one non-empty subset: {7}. Its XOR sum is 7. Since 7 is linearly independent and no other numbers are available to XOR with it to form 0, 0 cannot be formed by a non-empty subset. Thus, only 7 is counted, resulting in 1 distinct XOR sum.

4

Example 4

Input:

nums = [0, 0, 0]

Output:

1

Note:

The only non-empty subset XOR sum is 0 (e.g., {0} or {0,0} -> 0^0=0). All elements are 0, so the basis size is 0, but 0 can be formed by a non-empty subset. The count is 1.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 10^9
  • The maximum possible XOR sum will fit within a standard 32-bit signed integer. The final count of distinct XOR sums will fit within a standard 64-bit integer type (e.g., JavaScript's number or TypeScript's number which can represent up to 2^53 - 1 exactly, and 2^30 will fit easily).

What interviewers evaluate

  • Correctness of Linear Basis Application: The solution must accurately construct and utilize a linear basis (or equivalent concept) to identify the span of XOR sums.
  • Handling of Zero and Linear Dependence: Correctly determines if 0 is achievable as an XOR sum from a non-empty subset, and adjusts the final count accordingly.
  • Optimal Time Complexity (O(N * MaxBits)): Achieves an efficient algorithm, demonstrating understanding of complexity for bit manipulation problems, avoiding exponential time.
  • Proficiency with Bitwise Operations: Demonstrates clear and accurate use of bitwise operators (e.g., XOR, bit shifts) for manipulating numbers.
  • Edge Case Robustness: Handles specific edge cases such as arrays with single elements, arrays containing 0s, or arrays where all elements are linearly dependent.

Loading editor...