Re: [閒聊] 每日leetcode已回收
1863. Sum of All Subset XOR
稍微理解一下O(n)的解法
我們將subset sum拆解為每位的結果相加
先從bit 0看 可以將subset拆成包含a_n與不包含的兩種
因此如果a_n bit 0為1 則整個subset bit 0的1的數量為Len / 2 for any n
我們OR 所有數就可以知道該位是否要算
ans = or sum * n / 2
不過要一開始就想到還真難
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.46.164 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716176447.A.16C.html
推
05/20 11:54,
1年前
, 1F
05/20 11:54, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 247 之 1554 篇)：