Number of Effective Subsequences - Solution & Explanation

Problem Overview: You receive an integer array and must count how many subsequences satisfy the definition of an effective subsequence. The key challenge is that subsequences grow exponentially, so enumerating all possibilities quickly becomes infeasible. The goal is to aggregate subsequence properties using bit operations and dynamic programming rather than generating them explicitly.

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

The most direct method generates every subsequence using bitmask enumeration. For each mask from 0 to (1<<n)-1, compute the combined bitwise property of the chosen elements and check whether it satisfies the "effective" condition. This verifies correctness but scales poorly because the number of subsequences doubles with each element. Even with small arrays, 2^n combinations become impractical.

Approach 2: Dynamic Programming on Bitmasks (O(n * M) time, O(M) space)

A better strategy tracks subsequence states using a DP table indexed by bitmasks. Each state dp[mask] represents how many subsequences produce that mask as their combined bitwise result. While iterating through the array, update states by combining the current number with existing masks using bitwise operations such as & or | depending on the problem definition. This avoids explicit subsequence generation and instead aggregates counts. The number of masks M depends on the bit width of the numbers, typically bounded by 2^B where B is the number of relevant bits.

Approach 3: Bit Frequency + Combinatorics Optimization (O(n * B) time, O(B) space)

The optimal solution leverages the observation that subsequence validity depends only on specific bit patterns. Instead of storing every mask, track how many numbers contribute to each bit position. Combinatorics then determines how many subsequences preserve the required bit structure. Precompute powers of two to represent inclusion or exclusion of elements and accumulate valid counts per bit configuration. This approach reduces state space dramatically and relies heavily on bit manipulation and combinatorics rather than full mask enumeration.

The transitions resemble typical dynamic programming patterns: process each element once, update aggregated counts, and avoid recomputing overlapping subsequence states.

Recommended for interviews: Start by explaining the brute force enumeration to show you understand the subsequence search space. Then transition to the bitmask DP idea that aggregates states instead of generating them. The optimized combinatorics-based counting is usually what interviewers expect for a Hard problem because it reduces exponential growth to near-linear complexity with respect to the array size.