Frontend School

Max XOR Subset Sum with Max Set Bits

DSA
hard

Max XOR Subset Sum with Max Set Bits

Hard
Bit Manipulation
Subset
Linear Algebra

Overview

In distributed systems and large-scale data processing at Netflix, ensuring data integrity and optimizing storage for unique identifiers is critical. Sometimes, specific bit patterns within data can indicate properties, errors, or unique characteristics. This problem challenges you to analyze bit patterns across a collection of numbers to find a 'special' XOR sum, which is crucial for tasks like efficient data representation or advanced error detection codes.

What you need to do / Task

You are given an array of non-negative integers nums. Your task is to find a non-empty subset of these numbers such that their XOR sum (X) satisfies two conditions:

  1. X has the maximum possible number of set bits (1s) among all possible non-empty subset XOR sums.
  2. If there are multiple X values that achieve this maximum number of set bits, you should return the smallest one.

Input & output

  • Input: nums - An array of non-negative integers.
  • Output: A single non-negative integer representing the XOR sum that meets the specified criteria.

Clarifications

  • Empty subset: The problem explicitly states a 'non-empty subset', meaning the XOR sum of an empty set (which is 0) should not be considered unless 0 is the XOR sum of a non-empty subset and happens to satisfy the conditions.
  • Duplicate numbers: If nums contains duplicate numbers, they are treated as distinct elements for subset formation (e.g., in [2, 2], you can form a subset {2} (first 2), {2} (second 2), or {2, 2}).
  • Smallest value tie-break: If multiple XOR sums have the same maximum number of set bits, return the numerically smallest among them.

Examples

1

Example 1

Input:

nums = [1, 2, 3]

Output:

3

Note:

Given nums = [1, 2, 3]:

  • Subsets and their XOR sums:
    • {1} -> 1 (01_2, 1 set bit)
    • {2} -> 2 (10_2, 1 set bit)
    • {3} -> 3 (11_2, 2 set bits)
    • {1,2} -> 1^2 = 3 (11_2, 2 set bits)
    • {1,3} -> 1^3 = 2 (10_2, 1 set bit)
    • {2,3} -> 2^3 = 1 (01_2, 1 set bit)
    • {1,2,3} -> 1^2^3 = 0 (00_2, 0 set bits)
  • The maximum number of set bits is 2. The numbers achieving this are 3 (from {3}) and 3 (from {1,2}).
  • The numerically smallest among these is 3.
2

Example 2

Input:

nums = [6, 7]

Output:

7

Note:

Given nums = [6, 7]:

  • 6 = 110_2 (2 set bits)
  • 7 = 111_2 (3 set bits)
  • 6^7 = 1_2 (1 set bit)
  • The maximum number of set bits is 3, achieved by 7. Therefore, 7 is the result.
3

Example 3

Input:

nums = [0, 0, 0]

Output:

0

Note:

Given nums = [0, 0, 0]:

  • Any non-empty subset XOR sum will be 0.
  • 0 (00_2) has 0 set bits. This is the only possible outcome.
4

Example 4

Input:

nums = [2, 4, 8]

Output:

14

Note:

Given nums = [2, 4, 8]:

  • 2 (0010_2, 1 bit)
  • 4 (0100_2, 1 bit)
  • 8 (1000_2, 1 bit)
  • 2^4 = 6 (0110_2, 2 bits)
  • 2^8 = 10 (1010_2, 2 bits)
  • 4^8 = 12 (1100_2, 2 bits)
  • 2^4^8 = 14 (1110_2, 3 bits)
  • The maximum number of set bits is 3, achieved by 14. Therefore, 14 is the result.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 20
  • 0 <= nums[i] < 2^30
  • All input numbers are non-negative integers.

Out of scope

  • Handling negative numbers in the input array.
  • Input arrays with extremely large N (e.g., N > 60).
  • Performance considerations for nums[i] values larger than 30 bits.

What interviewers evaluate

  • Correctness: The solution must correctly identify the XOR sum based on both maximum set bits and the tie-breaking rule for numerical value.
  • Bit Manipulation Proficiency: Demonstrates effective use of bitwise operations (XOR, bit shifting, counting set bits).
  • Algorithmic Efficiency: The chosen approach should be efficient enough for the given constraints (e.g., N=20), ideally leveraging properties of XOR sums and bit patterns.
  • Code Quality: Readability, modularity, and proper handling of edge cases.

Loading editor...