diff options
author | Jack Sangdahl <[email protected]> | 2025-04-04 23:34:14 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-04 23:34:14 -0600 |
commit | f8d9a0c6ef10d434749cbc0d9ae51b1482aad1b6 (patch) | |
tree | a8549ed421b21c5bafa829e5cacda3ae53d9ef01 | |
parent | 6e2b4dac24efabc44781551afdb9d1723849ae62 (diff) | |
download | leetcode-f8d9a0c6ef10d434749cbc0d9ae51b1482aad1b6.tar.gz leetcode-f8d9a0c6ef10d434749cbc0d9ae51b1482aad1b6.zip |
1863. sum of all subset xor totals
-rw-r--r-- | sum_subset_xor.c | 23 | ||||
-rw-r--r-- | sum_subset_xor.py | 22 |
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__": |