Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀
100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney
*Problem: *
https://www.geeksforgeeks.org/problems/subset-xor--175953/1
Subset XOR
Difficulty: Medium Accuracy: 79.36%
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] < Bi.
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
Solution:
class Solution:
def subsetXOR(self, n: int):
xr = [n,1,n+1,0][n%4]
need = xr ^ n
if 1 <= need <= n:
return [i for i in range(1,n+1) if i!=need]
return [i for i in range(1,n+1)]
Top comments (0)