aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-04 23:34:14 -0600
committerJack Sangdahl <[email protected]>2025-04-04 23:34:14 -0600
commitf8d9a0c6ef10d434749cbc0d9ae51b1482aad1b6 (patch)
treea8549ed421b21c5bafa829e5cacda3ae53d9ef01
parent6e2b4dac24efabc44781551afdb9d1723849ae62 (diff)
downloadleetcode-f8d9a0c6ef10d434749cbc0d9ae51b1482aad1b6.tar.gz
leetcode-f8d9a0c6ef10d434749cbc0d9ae51b1482aad1b6.zip
1863. sum of all subset xor totals
-rw-r--r--sum_subset_xor.c23
-rw-r--r--sum_subset_xor.py22
2 files changed, 7 insertions, 38 deletions
diff --git a/sum_subset_xor.c b/sum_subset_xor.c
index cb51647..7c32618 100644
--- a/sum_subset_xor.c
+++ b/sum_subset_xor.c
@@ -8,26 +8,11 @@
* if 'a' can be obtained from 'b' by deleting some elements of 'b'.
*/
-void backtrack(int *nums, int numsSize, int tar, int idx, int *cnt) {
- if (idx == numsSize) {
- return;
- } else {
- for (int i = idx; i < numsSize; i++) {
- tar ^= nums[i];
- *cnt += tar;
- backtrack(nums, numsSize, tar, i + 1, cnt);
- tar ^= nums[i];
- }
- }
-}
-
int subsetXORSum(int *nums, int numsSize) {
- int ans = 0;
- for (int i = 0; i < numsSize; i++) {
- ans += nums[i];
- backtrack(nums, numsSize, nums[i], i + 1, &ans);
- }
- return ans;
+ int all = 0, mult = 1 << (numsSize - 1);
+ for (int i = 0; i < numsSize; i++)
+ all |= nums[i];
+ return all * mult;
}
int main() {
diff --git a/sum_subset_xor.py b/sum_subset_xor.py
index deb88ed..0560197 100644
--- a/sum_subset_xor.py
+++ b/sum_subset_xor.py
@@ -1,4 +1,6 @@
# 1863. Sum of All Subset XOR Totals
+from functools import reduce
+from operator import or_
"""
the xor total of an array is defined as the bitwise xor of all its elements
@@ -14,25 +16,7 @@ class Solution(object):
:type nums: List[int]
:rtype: int
"""
-
- def backtrack(nums, idx, tar, cnt):
- if idx == len(nums):
- cnt.append(tar[:])
- return
- tar.append(nums[idx])
- backtrack(nums, idx + 1, tar, cnt)
- tar.pop()
- backtrack(nums, idx + 1, tar, cnt)
-
- cnt = []
- backtrack(nums, 0, [], cnt)
- ans = 0
- for i in cnt:
- total = 0
- for n in i:
- total ^= n
- ans += total
- return ans
+ return reduce(or_, nums) << (len(nums) - 1)
if __name__ == "__main__":