Submask Sum Queries
Reported by candidates from Intuit's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Intuit OA reported in September 2026 has a question called Submask Sum Queries, and the trap is sitting in the n = 0 case and the negative values. It's a sum-over-subsets problem. You get 2^n values and up to 1000 mask queries, and each query wants the sum over every submask. A naive loop per query looks fine until you think about it. If the pattern doesn't click when the timer's running, StealthCoder is the quiet safety net on your screen, invisible to the proctor, so a blank doesn't sink the attempt.
The problem
You are given a nonnegative bit count n, an integer array values of length 2^n, and an array of query masks queries. A mask s is a submask of m when every set bit of s is also set in m. For each query mask m, return the sum of values[s] over every submask s of m. Return answers in the same order as the queries. Function sumSubmaskValues(n: int, values: long[], queries: int[]) → long[] Examples Example 1 n = 2 values = [1,2,3,4] queries = [3,1] return = [10,3] Every mask from 0 through 3 is a submask of 3, so the first sum is 1 + 2 + 3 + 4 = 10. The submasks of 1 are 0 and 1, producing 1 + 2 = 3. Example 2 n = 1 values = [-2,5] queries = [0,1] return = [-2,3] Mask 0 has only itself as a submask, so the first result is -2. Mask 1 has submasks 0 and 1, producing -2 + 5 = 3. Constraints 0 ≤ n ≤ 12 and values.length = 2^n. -10^9 ≤ values[i] ≤ 10^9. 1 ≤ queries.length ≤ 1000 and every query is a valid mask in [0, 2^n - 1]. Every answer fits in a signed 64-bit integer.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is the SOS DP, also called the zeta transform over subsets. Copy values into dp, then for each bit i from 0 to n-1, loop over every mask, and if the mask has bit i set, do dp[mask] += dp[mask ^ (1<<i)]. That's O(n * 2^n), about 50k operations at n = 12. Then each query is just dp[query]. The pitfalls are small but real. Use 64-bit longs, since sums of 4096 values near 10^9 overflow 32-bit. Don't skip the n = 0 case, where values has one element and the only mask is 0. Negative values rule out any pruning or early exit tricks. Brute-force submask enumeration works on paper, but precompute once instead. If you freeze on the bit loop order during the live OA, StealthCoder can hand you the clean transform as a hedge.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Submask Sum Queries cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Intuit's OA.
Intuit reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Submask Sum Queries FAQ
What's the trick in Submask Sum Queries?+
Precompute a subset-sum table once with SOS DP. For each bit, add the value of the mask with that bit cleared into every mask that has the bit set. After n passes, dp[m] holds the sum over all submasks of m. Each query becomes a single array lookup.
Can I just enumerate submasks per query?+
Yes, using s = (s - 1) & m, and it's correct. With n up to 12 and 1000 queries, the worst case is about 4 million steps, which is likely fine. SOS DP is cleaner and safer, and it's the version interviewers expect you to know.
What edge cases break a naive solution here?+
n = 0 gives a single value and only mask 0. Negative values mean you can't assume sums grow. Query mask 0 must return values[0] only. Overflow matters too, so use 64-bit integers for the dp array and the output.
How hard is this really for the Intuit OA?+
Medium if you've seen SOS DP, hard if you haven't. The code is about ten lines. The difficulty is recognizing the bitmask pattern instead of reaching for nested loops. Small constraints can mislead you into thinking brute force is the intended answer.
How do I prepare in 48 hours?+
Write the SOS DP loop from memory twice. Test it on both examples, then on n = 0. Practice the bit check (mask >> i) & 1 and the loop order, with bits on the outside. Also review the supermask variant, since it's a common twist.