Subset XOR | Explained and Solved Interview Coding

Subset XOR

Difficulty: MediumAccuracy: 73.09%Submissions: 7K+Points: 4

Given an positive integer n, find a subset of numbers from 1 to n (inclusive), where each number can be used at most once, such that:

• The XOR of all elements in the subset is exactly n.
• The size of the subset is as large as possible.
• If multiple such subsets exist, choose the lexicographically smallest one.

Lexicographical Order : A subset A[] is lexicographically smaller than subset B[] if at the first index where they differ, A[i] < B[i] (based on character ASCII/Unicode values).
If all elements match but one subset ends earlier, the shorter subset is considered smaller.

Examples:

Input: n = 4
Output: [1, 2, 3, 4]
Explanation: We choose all the elements from 1 to 4. Its xor value is equal to n. This is the maximum possible size of the subset.

Input: n = 3
Output: [1, 2]
Explanation: 1 ^ 2 = 3, This is the smallest lexicographical answer possible with maximum size of subset i.e 2.

Constraints:
1 ≤ n ≤ 105

Expected Complexities

Topic Tags

If you are facing any issue on this page. Please let us know.