LeetCode Entry

1863. Sum of All Subset XOR Totals

05.04.2025 easy 2025 kotlin rust

Sum of all subsets xors

1863. Sum of All Subset XOR Totals easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/949

Problem TLDR

Sum of all subsets xors #easy #bit #math

Intuition

There are total 2^(n - 1) subsets. We can

  • iterate over mask of set bits, each bit is a position
  • use recursion with backtracking: take value or skip, compute xor so far

The math trick solution: if bit is present it contributes 2^(n - 1) times, find all present bits with or.

Approach

  • the mask solution is easier to not make a mistake

Complexity

  • Time complexity: \(O(2^n)\)

  • Space complexity: \(O(n)\), or O(1) for iterative mask solution

Code


    fun subsetXORSum(a: IntArray) = (0..(1 shl a.size)).sumOf { m ->
        a.indices.map { a[it] * (m shr it and 1) }.reduce(Int::xor)
    }



    fun subsetXORSum(a: IntArray) = (0..(1 shl a.size)).sumOf { m ->
        1 * a.indices.fold(0) { x, i -> x xor a[i] * (m shr i and 1) }
    }



    fun subsetXORSum(a: IntArray): Int {
        fun d(i: Int, x: Int): Int = if (i == a.size) x
            else d(i + 1, x) + d(i + 1, x xor a[i])
        return d(0, 0)
    }



    pub fn subset_xor_sum(a: Vec<i32>) -> i32 {
        (0..1 << a.len()).map(|m| (0..a.len())
        .fold(0, |x, i| x ^ a[i] * (m >> i & 1))).sum()
    }



    pub fn subset_xor_sum(a: Vec<i32>) -> i32 {
        fn d(a: &[i32], x: i32) -> i32
            { if a.len() > 0  { d(&a[1..], x) + d(&a[1..], x ^ a[0]) } else { x }}
        d(&a, 0)
    }



    int subsetXORSum(vector<int>& a) {
        for (int x: a) a[0] |= x; return a[0] << (size(a) - 1);
    }