Sum of Beautiful Subsequences - Solution & Explanation

Problem Overview: You are given an array and must compute the total sum contributed by all beautiful subsequences. A subsequence becomes beautiful based on a mathematical property between its elements (typically divisibility or gcd relationships). The challenge is that the number of subsequences grows exponentially, so you must aggregate contributions efficiently instead of enumerating them.

Approach 1: Brute Force Subsequence Enumeration (O(2^n * n) time, O(n) space)

Generate every possible subsequence using recursion or bitmasking. For each subsequence, check whether it satisfies the beauty condition using a mathematical check such as gcd or divisor relations. If it is valid, compute its contribution to the final sum. This approach directly models the definition of the problem but quickly becomes infeasible once n exceeds ~20 because the number of subsequences doubles with every element.

Approach 2: Dynamic Programming with Divisor Enumeration (O(n * sqrt(V)) time, O(V) space)

Instead of generating subsequences explicitly, track how many valid subsequences end with a given value. For each number x, enumerate its divisors and update dynamic programming states representing subsequences whose last element maintains the beauty condition. The key insight: subsequences that remain beautiful often depend only on shared divisibility or gcd relationships. This allows transitions from previous compatible values to the current value without recomputing the whole subsequence. The DP array stores counts or sums of subsequences grouped by value.

Approach 3: Fenwick Tree (Binary Indexed Tree) + Number Theory (O(n log V) time, O(V) space)

The optimal solution uses a Binary Indexed Tree to maintain prefix aggregates of subsequence contributions indexed by value. For each element a[i], compute all relevant divisors using number theory techniques. Query the Fenwick tree to retrieve the total contribution from previously processed elements that can extend into a beautiful subsequence with a[i]. Update the structure with the new subsequences formed by including a[i]. This avoids scanning all previous elements and reduces transitions to logarithmic time.

The Fenwick tree efficiently supports prefix sum queries and updates, making it ideal when subsequence transitions depend on ordered values. Combined with divisor enumeration, it compresses what would otherwise be quadratic DP into near-linear time.

Recommended for interviews: Start by explaining the brute force enumeration to show you understand subsequences and the beauty condition. Then move to the optimized dynamic programming idea. Interviewers typically expect the Fenwick Tree + number theory optimization because it reduces the transition cost and scales to large arrays.