Product of Subset Maxima
Reported by candidates from Arcesium's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Arcesium reported this one in July 2025, and the title sounds scarier than the problem is. You're asked for the product of maxima over every non-empty subset, mod 10^9 + 7. The solution hinges on a sorted array, not a tree or a DFS, even though the hint says depth-first-search. Enumerating subsets is a trap at 2^n. If you've got an Arcesium OA coming, learn the counting trick below. StealthCoder sits invisible on your screen as a safety net if your mind goes blank mid-assessment.
The problem
Given an array values of positive integers, consider every non-empty subset of array indices. The value of a subset is the maximum array value selected by that subset. Return the product of the values of all non-empty subsets, modulo 10^9 + 7. Two equal values at different indices are still distinct selectable elements. Function productOfSubsetMaxima(values: int[]) → int Examples Example 1 values = [1,2,3] return = 324 The seven non-empty subsets have maxima 1, 2, 3, 2, 3, 3, 3. Their product is 324. Example 2 values = [1,1,1,1] return = 1 Every non-empty subset has maximum value 1. Constraints values.length >= 1. Every element of values is positive.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Sort the array ascending. For the element at sorted index i (0-based), it's the maximum of exactly 2^i subsets, because you can pick any combination of the i smaller elements before it. Ties are fine since equal values at different indices are distinct, and sorted order gives each one a unique rank. So the answer is the product over i of sorted[i]^(2^i), mod 10^9 + 7. The pitfall is the exponent. 2^i gets huge, so use modular fast exponentiation, and reduce the exponent mod (10^9 + 6) by Fermat's little theorem, or simply track a running power. Cleaner trick: keep p = 2^i mod (MOD-1) and call pow(v, p, MOD). Check example 1: 1^1 * 2^2 * 3^4 = 324. StealthCoder is your hedge in the live OA if the exponent reduction slips your mind. Complexity is O(n log n) for the sort plus O(n log MOD) for the powers.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Product of Subset Maxima 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. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Arcesium's OA.
Arcesium reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Product of Subset Maxima FAQ
What's the trick in Product of Subset Maxima?+
Sort ascending. The element at sorted index i is the max of exactly 2^i subsets, since any subset of the smaller elements can join it. The answer is the product of sorted[i] raised to 2^i, modulo 10^9 + 7. No subset enumeration needed.
Why does the hint say depth-first-search?+
Brute force would recurse over every subset with DFS, but that's 2^n and dies on large inputs. The real solution is sorting plus modular exponentiation. Treat DFS as the naive baseline you mention and then discard.
How do I handle the huge exponent 2^i?+
Reduce the exponent modulo 10^9 + 6, since the modulus 10^9 + 7 is prime and Fermat applies. Keep a running exponent that doubles each step, taken mod 10^9 + 6, and call fast pow on each value. Values are positive, so none is divisible by the modulus unless it equals a multiple of it, which you should consider.
Do duplicate values break the counting?+
No. The problem says equal values at different indices are distinct elements. After sorting, break ties by position so each duplicate gets its own rank. Example 2 with four 1s gives 1 regardless, which is a good sanity test.
How do I prepare for this in 48 hours?+
Write it once from scratch: sort, loop, fast pow, mod. Test on [1,2,3] expecting 324 and [1,1,1,1] expecting 1. Then practice the general contribution technique, where you count how many subsets each element dominates. It shows up in many subset-sum-of-max or min problems.