2818. Apply Operations to Maximize Score

HardStackGreedyArrayMathNumber TheorySortingMonotonic Stack

Problem Description

You are given an array nums containing n positive integers and an integer k. Your goal is to maximize a score that starts at 1 by performing at most k operations.

Each operation works as follows:

Select any subarray nums[l, ..., r] that hasn't been chosen before
From this subarray, pick the element x with the highest prime score (if there's a tie, choose the one with the smallest index)
Multiply your current score by x

The prime score of a number is defined as the count of its distinct prime factors. For example:

The prime score of 300 is 3 because 300 = 2 × 2 × 3 × 5 × 5, which has three distinct prime factors: 2, 3, and 5

The challenge is to strategically select subarrays and elements to maximize your final score after performing at most k operations. Since the result can be very large, return it modulo 10^9 + 7.

The key insight is that for each element in the array, you need to determine how many subarrays it can be the maximum prime score element for. This involves finding the boundaries where an element has the highest prime score compared to its neighbors. The solution uses a monotonic stack to efficiently compute these boundaries for each element, then greedily selects elements with the largest values to maximize the score.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The first observation is that we want to multiply our score by the largest numbers as many times as possible. However, we're constrained by the rule that each chosen element must have the highest prime score in its selected subarray.

Think about it this way: for any element nums[i], in how many different subarrays can it be the element with the highest prime score? If we can answer this question, we know the maximum number of times we can potentially use nums[i] in our operations.

For an element at position i to have the highest prime score in a subarray [l, r]:

No element to its left in the range [l, i-1] should have a higher prime score
No element to its right in the range [i+1, r] should have a higher prime score

This means we need to find:

The leftmost position left[i] where all elements between left[i]+1 and i-1 have a lower prime score than nums[i]
The rightmost position right[i] where all elements between i+1 and right[i]-1 have a lower or equal prime score than nums[i]

Once we have these boundaries, the number of valid subarrays where nums[i] is the maximum prime score element is (i - left[i]) × (right[i] - i). This is because we can choose any starting position from left[i]+1 to i and any ending position from i to right[i]-1.

Now comes the greedy part: since we want to maximize our score, we should prioritize using larger numbers. We sort elements by their values in descending order and greedily use each element as many times as possible (up to its maximum count of valid subarrays) until we've performed k operations.

The monotonic stack technique efficiently computes the boundaries for each element by maintaining elements in order of their prime scores, allowing us to find the nearest greater element on both sides in linear time.

Learn more about Stack, Greedy, Math, Sorting and Monotonic Stack patterns.

Solution Approach

The implementation consists of three main phases:

Phase 1: Calculate Prime Scores First, we compute the prime score for each element using a helper function primeFactors(n). This function finds all distinct prime factors by:

Iterating from 2 to √n
Dividing n by each factor until it's no longer divisible
Adding each distinct prime to a set
If n > 1 after the loop, it's itself a prime factor

Phase 2: Find Boundaries Using Monotonic Stack For each element at position i, we need to find:

left[i]: The rightmost index to the left where an element has a prime score ≥ nums[i]'s prime score
right[i]: The leftmost index to the right where an element has a prime score > nums[i]'s prime score

We use monotonic stacks to efficiently compute these boundaries:

For left boundaries:

Traverse the array from left to right
Maintain a stack of (prime_score, index) pairs
For each element, pop all stack elements with smaller prime scores
The top of the stack (if exists) gives us left[i]
Push current element onto stack

For right boundaries:

Traverse the array from right to left (reverse iteration)
Similar process but pop elements with prime scores ≤ current element's score
This ensures elements with equal prime scores but smaller indices are prioritized

Phase 3: Greedy Selection After computing boundaries, we sort all elements by their values in descending order. For each element at position i:

Calculate the number of valid subarrays: cnt = (i - left[i]) × (right[i] - i)
If cnt ≤ k, use this element cnt times: ans = ans × nums[i]^cnt mod (10^9 + 7)
If cnt > k, use this element only k times: ans = ans × nums[i]^k mod (10^9 + 7) and stop
Update k = k - cnt after each iteration

The use of modular exponentiation pow(x, cnt, mod) ensures efficient computation of large powers while keeping results within bounds.

This greedy approach works because once we know how many times each element can be used, it's optimal to use larger elements as many times as possible first.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: nums = [8, 3, 9, 6], k = 2

Step 1: Calculate Prime Scores

8 = 2³ → prime score = 1 (only prime factor: 2)
3 = 3 → prime score = 1 (only prime factor: 3)
9 = 3² → prime score = 1 (only prime factor: 3)
6 = 2 × 3 → prime score = 2 (prime factors: 2, 3)

So prime scores are: [1, 1, 1, 2]

Step 2: Find Boundaries Using Monotonic Stack

Finding left boundaries (traverse left to right):

Index 0: Stack empty, left[0] = -1
Index 1: Prime score 1 = stack top's score 1, left[1] = 0
Index 2: Prime score 1 = stack top's score 1, left[2] = 1
Index 3: Prime score 2 > all previous, pop all, left[3] = -1

Result: left = [-1, 0, 1, -1]

Finding right boundaries (traverse right to left):

Index 3: Stack empty, right[3] = 4
Index 2: Prime score 1 < stack top's score 2, right[2] = 3
Index 1: Prime score 1 < stack top's score 2, right[1] = 3
Index 0: Prime score 1 < stack top's score 2, right[0] = 3

Result: right = [3, 3, 3, 4]

Step 3: Calculate Valid Subarrays for Each Element

Element at index 0 (value 8): (0 - (-1)) × (3 - 0) = 1 × 3 = 3 subarrays
Element at index 1 (value 3): (1 - 0) × (3 - 1) = 1 × 2 = 2 subarrays
Element at index 2 (value 9): (2 - 1) × (3 - 2) = 1 × 1 = 1 subarray
Element at index 3 (value 6): (3 - (-1)) × (4 - 3) = 4 × 1 = 4 subarrays

Step 4: Greedy Selection Sort elements by value (descending): [(9, 1 subarray), (8, 3 subarrays), (6, 4 subarrays), (3, 2 subarrays)]

With k = 2 operations:

First pick: 9 can be used 1 time, score = 1 × 9 = 9, remaining k = 1
Second pick: 8 can be used up to 3 times, but we only have k = 1 left, score = 9 × 8 = 72

Final Answer: 72

This example shows how the algorithm identifies which element has the highest prime score in each possible subarray, then greedily selects the largest values to maximize the final score.

Solution Implementation

1def count_distinct_prime_factors(n: int) -> int:
2    """
3    Count the number of distinct prime factors of n.
4  
5    Args:
6        n: The number to factorize
7  
8    Returns:
9        The count of distinct prime factors
10    """
11    i = 2
12    distinct_factors = set()
13  
14    # Check divisors up to sqrt(n)
15    while i * i <= n:
16        # Extract all occurrences of prime factor i
17        while n % i == 0:
18            distinct_factors.add(i)
19            n //= i
20        i += 1
21  
22    # If n > 1, then it's a prime factor itself
23    if n > 1:
24        distinct_factors.add(n)
25  
26    return len(distinct_factors)
27
28
29class Solution:
30    def maximumScore(self, nums: List[int], k: int) -> int:
31        """
32        Calculate the maximum score by selecting subsequences and computing products.
33      
34        The score is based on selecting elements and raising them to powers determined
35        by the number of valid subsequences containing each element.
36      
37        Args:
38            nums: List of positive integers
39            k: Maximum number of operations allowed
40      
41        Returns:
42            The maximum score modulo 10^9 + 7
43        """
44        MOD = 10**9 + 7
45        n = len(nums)
46      
47        # Create array with (index, prime_factor_count, value) for each element
48        elements_with_info = [(i, count_distinct_prime_factors(nums[i]), nums[i]) 
49                               for i in range(n)]
50      
51        # Arrays to store boundaries for each element
52        # left[i]: rightmost index j < i where prime_factor_count[j] >= prime_factor_count[i]
53        # right[i]: leftmost index j > i where prime_factor_count[j] > prime_factor_count[i]
54        left_boundary = [-1] * n
55        right_boundary = [n] * n
56      
57        # Calculate left boundaries using monotonic stack
58        # Stack maintains elements with decreasing prime factor counts
59        stack = []
60        for index, prime_count, value in elements_with_info:
61            # Pop elements with smaller prime factor count
62            while stack and stack[-1][0] < prime_count:
63                stack.pop()
64          
65            # If stack not empty, top element is the left boundary
66            if stack:
67                left_boundary[index] = stack[-1][1]
68          
69            stack.append((prime_count, index))
70      
71        # Calculate right boundaries using monotonic stack (process from right to left)
72        stack = []
73        for index, prime_count, value in reversed(elements_with_info):
74            # Pop elements with smaller or equal prime factor count
75            while stack and stack[-1][0] <= prime_count:
76                stack.pop()
77          
78            # If stack not empty, top element is the right boundary
79            if stack:
80                right_boundary[index] = stack[-1][1]
81          
82            stack.append((prime_count, index))
83      
84        # Sort elements by value in descending order to maximize score
85        elements_with_info.sort(key=lambda x: -x[2])
86      
87        # Calculate the maximum score
88        result = 1
89        for index, prime_count, value in elements_with_info:
90            left_bound = left_boundary[index]
91            right_bound = right_boundary[index]
92          
93            # Calculate number of subsequences where this element is the minimum
94            # based on prime factor count
95            # Number of ways to choose left part * number of ways to choose right part
96            subsequence_count = (index - left_bound) * (right_bound - index)
97          
98            if subsequence_count <= k:
99                # Use all possible subsequences for this element
100                result = result * pow(value, subsequence_count, MOD) % MOD
101                k -= subsequence_count
102            else:
103                # Use only k remaining subsequences
104                result = result * pow(value, k, MOD) % MOD
105                break
106      
107        return result
108

1class Solution {
2    private final int MOD = (int) 1e9 + 7;
3
4    public int maximumScore(List<Integer> nums, int k) {
5        int n = nums.size();
6      
7        // Create array storing [index, prime factor count, value] for each number
8        int[][] elements = new int[n][3];
9        for (int i = 0; i < n; i++) {
10            elements[i] = new int[] {i, countUniquePrimeFactors(nums.get(i)), nums.get(i)};
11        }
12      
13        // Find the left boundary for each element (previous element with >= prime factors)
14        int[] leftBoundary = new int[n];
15        Arrays.fill(leftBoundary, -1);
16      
17        // Find the right boundary for each element (next element with > prime factors)
18        int[] rightBoundary = new int[n];
19        Arrays.fill(rightBoundary, n);
20      
21        // Use monotonic stack to find left boundaries
22        Deque<Integer> stack = new ArrayDeque<>();
23        for (int[] element : elements) {
24            int index = element[0];
25            int primeFactorCount = element[1];
26          
27            // Pop elements with fewer prime factors
28            while (!stack.isEmpty() && elements[stack.peek()][1] < primeFactorCount) {
29                stack.pop();
30            }
31          
32            // The remaining top element (if exists) is the left boundary
33            if (!stack.isEmpty()) {
34                leftBoundary[index] = stack.peek();
35            }
36          
37            stack.push(index);
38        }
39      
40        // Clear stack for reuse
41        stack.clear();
42      
43        // Use monotonic stack to find right boundaries (traverse from right to left)
44        for (int i = n - 1; i >= 0; i--) {
45            int primeFactorCount = elements[i][1];
46          
47            // Pop elements with fewer or equal prime factors
48            while (!stack.isEmpty() && elements[stack.peek()][1] <= primeFactorCount) {
49                stack.pop();
50            }
51          
52            // The remaining top element (if exists) is the right boundary
53            if (!stack.isEmpty()) {
54                rightBoundary[i] = stack.peek();
55            }
56          
57            stack.push(i);
58        }
59      
60        // Sort elements by value in descending order
61        Arrays.sort(elements, (a, b) -> b[2] - a[2]);
62      
63        // Calculate the maximum score
64        long result = 1;
65      
66        for (int[] element : elements) {
67            int index = element[0];
68            int value = element[2];
69            int left = leftBoundary[index];
70            int right = rightBoundary[index];
71          
72            // Calculate number of subarrays where this element is the max prime score
73            long subarrayCount = (long) (index - left) * (right - index);
74          
75            if (subarrayCount <= k) {
76                // Use this element for all possible subarrays
77                result = result * modularPower(value, subarrayCount) % MOD;
78                k -= subarrayCount;
79            } else {
80                // Use this element for remaining k subarrays and stop
81                result = result * modularPower(value, k) % MOD;
82                break;
83            }
84        }
85      
86        return (int) result;
87    }
88
89    /**
90     * Counts the number of unique prime factors of a given number
91     * @param n the number to factorize
92     * @return count of unique prime factors
93     */
94    private int countUniquePrimeFactors(int n) {
95        Set<Integer> uniquePrimes = new HashSet<>();
96      
97        // Check for factor 2 and all odd factors up to sqrt(n)
98        int factor = 2;
99        while (factor * factor <= n) {
100            while (n % factor == 0) {
101                uniquePrimes.add(factor);
102                n /= factor;
103            }
104            factor++;
105        }
106      
107        // If n is still greater than 1, it's a prime factor
108        if (n > 1) {
109            uniquePrimes.add(n);
110        }
111      
112        return uniquePrimes.size();
113    }
114
115    /**
116     * Calculates (base^exponent) % MOD using binary exponentiation
117     * @param base the base number
118     * @param exponent the exponent
119     * @return (base^exponent) % MOD
120     */
121    private int modularPower(long base, long exponent) {
122        long result = 1;
123      
124        while (exponent > 0) {
125            // If exponent is odd, multiply result by base
126            if ((exponent & 1) == 1) {
127                result = result * base % MOD;
128            }
129          
130            // Square the base and halve the exponent
131            base = base * base % MOD;
132            exponent >>= 1;
133        }
134      
135        return (int) result;
136    }
137}
138

1class Solution {
2public:
3    int maximumScore(vector<int>& nums, int k) {
4        const int MOD = 1e9 + 7;
5        int n = nums.size();
6      
7        // Store tuples of (index, prime factor count, value) for each element
8        vector<tuple<int, int, int>> elements(n);
9        for (int i = 0; i < n; ++i) {
10            elements[i] = {i, countUniquePrimeFactors(nums[i]), nums[i]};
11        }
12      
13        // Find the nearest left element with more prime factors using monotonic stack
14        vector<int> leftBoundary(n, -1);
15        stack<int> monotonicStack;
16      
17        for (auto [index, primeCount, _] : elements) {
18            // Pop elements with fewer prime factors
19            while (!monotonicStack.empty() && 
20                   get<1>(elements[monotonicStack.top()]) < primeCount) {
21                monotonicStack.pop();
22            }
23            // The top element (if exists) is the nearest left element with more prime factors
24            if (!monotonicStack.empty()) {
25                leftBoundary[index] = monotonicStack.top();
26            }
27            monotonicStack.push(index);
28        }
29      
30        // Find the nearest right element with more prime factors using monotonic stack
31        vector<int> rightBoundary(n, n);
32        monotonicStack = stack<int>();  // Reset the stack
33      
34        for (int i = n - 1; i >= 0; --i) {
35            int primeCount = get<1>(elements[i]);
36            // Pop elements with fewer or equal prime factors
37            while (!monotonicStack.empty() && 
38                   get<1>(elements[monotonicStack.top()]) <= primeCount) {
39                monotonicStack.pop();
40            }
41            // The top element (if exists) is the nearest right element with more prime factors
42            if (!monotonicStack.empty()) {
43                rightBoundary[i] = monotonicStack.top();
44            }
45            monotonicStack.push(i);
46        }
47      
48        // Sort elements by value in descending order to maximize score
49        sort(elements.begin(), elements.end(), 
50             [](const auto& a, const auto& b) {
51                 return get<2>(b) < get<2>(a);  // Descending order by value
52             });
53      
54        // Calculate the maximum score
55        long long result = 1;
56      
57        // Lambda function for modular exponentiation
58        auto modularPower = [&](long long base, int exponent) {
59            long long answer = 1;
60            while (exponent > 0) {
61                if (exponent & 1) {
62                    answer = answer * base % MOD;
63                }
64                base = base * base % MOD;
65                exponent >>= 1;
66            }
67            return answer;
68        };
69      
70        // Process elements in descending order of value
71        for (auto [index, _, value] : elements) {
72            int left = leftBoundary[index];
73            int right = rightBoundary[index];
74          
75            // Calculate number of subarrays where current element is the maximum prime score
76            long long subarrayCount = 1LL * (index - left) * (right - index);
77          
78            if (subarrayCount <= k) {
79                // Use this element for all possible subarrays
80                result = result * modularPower(value, subarrayCount) % MOD;
81                k -= subarrayCount;
82            } else {
83                // Use this element for remaining k subarrays and stop
84                result = result * modularPower(value, k) % MOD;
85                break;
86            }
87        }
88      
89        return result;
90    }
91
92private:
93    // Count the number of unique prime factors of a number
94    int countUniquePrimeFactors(int n) {
95        unordered_set<int> uniquePrimes;
96      
97        // Check for prime factors starting from 2
98        for (int divisor = 2; divisor * divisor <= n; ++divisor) {
99            while (n % divisor == 0) {
100                uniquePrimes.insert(divisor);
101                n /= divisor;
102            }
103        }
104      
105        // If n is still greater than 1, it's a prime factor itself
106        if (n > 1) {
107            uniquePrimes.insert(n);
108        }
109      
110        return uniquePrimes.size();
111    }
112};
113

1/**
2 * Calculates the maximum score by selecting subsequences based on prime factors
3 * @param nums - Array of positive integers
4 * @param k - Maximum number of operations allowed
5 * @returns Maximum score modulo 10^9 + 7
6 */
7function maximumScore(nums: number[], k: number): number {
8    const MOD = 10 ** 9 + 7;
9    const n = nums.length;
10  
11    // Create array to store [index, prime factor count, value] for each element
12    const elementInfo: number[][] = Array(n)
13        .fill(0)
14        .map(() => Array(3).fill(0));
15  
16    // Arrays to store the nearest larger element indices on left and right
17    const leftBoundary: number[] = Array(n).fill(-1);
18    const rightBoundary: number[] = Array(n).fill(n);
19  
20    // Populate element info with index, prime factor count, and value
21    for (let i = 0; i < n; ++i) {
22        elementInfo[i] = [i, primeFactors(nums[i]), nums[i]];
23    }
24  
25    // Find left boundary using monotonic stack
26    // For each element, find the nearest element on the left with more prime factors
27    const stack: number[] = [];
28    for (const [index, primeCount, _] of elementInfo) {
29        // Pop elements with fewer prime factors
30        while (stack.length && elementInfo[stack[stack.length - 1]][1] < primeCount) {
31            stack.pop();
32        }
33        // If stack has elements, the top is the left boundary
34        if (stack.length) {
35            leftBoundary[index] = stack[stack.length - 1];
36        }
37        stack.push(index);
38    }
39  
40    // Clear stack for reuse
41    stack.length = 0;
42  
43    // Find right boundary using monotonic stack (traverse from right to left)
44    // For each element, find the nearest element on the right with more prime factors
45    for (let i = n - 1; i >= 0; --i) {
46        const primeCount = elementInfo[i][1];
47        // Pop elements with fewer or equal prime factors
48        while (stack.length && elementInfo[stack[stack.length - 1]][1] <= primeCount) {
49            stack.pop();
50        }
51        // If stack has elements, the top is the right boundary
52        if (stack.length) {
53            rightBoundary[i] = stack[stack.length - 1];
54        }
55        stack.push(i);
56    }
57  
58    // Sort elements by value in descending order to process largest values first
59    elementInfo.sort((a, b) => b[2] - a[2]);
60  
61    // Calculate the maximum score
62    let result = 1n;
63    for (const [index, _, value] of elementInfo) {
64        const leftBound = leftBoundary[index];
65        const rightBound = rightBoundary[index];
66      
67        // Calculate how many subarrays contain this element as the minimum prime factor element
68        const subarrayCount = (index - leftBound) * (rightBound - index);
69      
70        if (subarrayCount <= k) {
71            // Use this element for all possible subarrays
72            result = (result * qpow(BigInt(value), subarrayCount, MOD)) % BigInt(MOD);
73            k -= subarrayCount;
74        } else {
75            // Use this element for remaining k operations
76            result = (result * qpow(BigInt(value), k, MOD)) % BigInt(MOD);
77            break;
78        }
79    }
80  
81    return Number(result);
82}
83
84/**
85 * Counts the number of distinct prime factors of a number
86 * @param n - The number to factorize
87 * @returns Count of distinct prime factors
88 */
89function primeFactors(n: number): number {
90    let divisor = 2;
91    const uniquePrimes: Set<number> = new Set();
92  
93    // Check all potential divisors up to sqrt(n)
94    while (divisor * divisor <= n) {
95        // If divisor is a factor, add it to the set and divide n
96        while (n % divisor === 0) {
97            uniquePrimes.add(divisor);
98            n = Math.floor(n / divisor);
99        }
100        ++divisor;
101    }
102  
103    // If n > 1 after division, it's a prime factor itself
104    if (n > 1) {
105        uniquePrimes.add(n);
106    }
107  
108    return uniquePrimes.size;
109}
110
111/**
112 * Fast exponentiation with modulo operation
113 * @param base - Base number as BigInt
114 * @param exponent - Exponent value
115 * @param modulo - Modulo value
116 * @returns (base^exponent) % modulo as BigInt
117 */
118function qpow(base: bigint, exponent: number, modulo: number): bigint {
119    let result = 1n;
120  
121    // Binary exponentiation algorithm
122    while (exponent > 0) {
123        // If current bit is 1, multiply result by base
124        if (exponent & 1) {
125            result = (result * base) % BigInt(modulo);
126        }
127        // Square the base for next bit
128        base = (base * base) % BigInt(modulo);
129        // Right shift to process next bit
130        exponent >>>= 1;
131    }
132  
133    return result;
134}
135

Time and Space Complexity

Time Complexity: O(n × √M + n × log n) where n is the length of the array and M is the maximum value in the array.

The primeFactors function has time complexity O(√M) for each number, where M is the value being factorized. The while loop runs up to √M iterations.
Computing prime factors for all n elements: O(n × √M)
Building the monotonic stack for left array: O(n) - each element is pushed and popped at most once
Building the monotonic stack for right array: O(n) - each element is pushed and popped at most once
Sorting the array by value in descending order: O(n × log n)
The final loop to calculate the answer: O(n) in the worst case, iterating through all elements
Total: O(n × √M + n × log n)

Since √M is typically much smaller than log n for reasonable input sizes, and considering the reference answer simplifies to O(n × log n), the dominant term is the sorting operation.

Space Complexity: O(n)

arr list storing tuples for each element: O(n)
left array: O(n)
right array: O(n)
Stack stk used in monotonic stack operations: O(n) in worst case
The ans set in primeFactors function: O(log M) at most, which is negligible
Total: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Conditions for Elements with Equal Prime Scores

One of the most common pitfalls in this problem is mishandling elements with equal prime scores when determining boundaries. The problem states that when multiple elements have the same prime score, we should choose the one with the smallest index.

The Pitfall: When calculating boundaries, developers often treat elements with equal prime scores inconsistently:

For the left boundary, we need >= comparison (elements with equal or greater prime scores)
For the right boundary, we need > comparison (strictly greater prime scores)

This asymmetry ensures that when multiple elements have the same prime score, only the leftmost one can be selected from any subarray containing them.

Incorrect Implementation Example:

# WRONG: Using the same comparison for both boundaries
for index, prime_count, value in elements_with_info:
    while stack and stack[-1][0] <= prime_count:  # Should be < for left boundary
        stack.pop()
    # ...

for index, prime_count, value in reversed(elements_with_info):
    while stack and stack[-1][0] < prime_count:  # Should be <= for right boundary
        stack.pop()
    # ...

Correct Implementation:

# Left boundary: pop elements with STRICTLY SMALLER prime scores
for index, prime_count, value in elements_with_info:
    while stack and stack[-1][0] < prime_count:  # < comparison
        stack.pop()
    # ...

# Right boundary: pop elements with SMALLER OR EQUAL prime scores
for index, prime_count, value in reversed(elements_with_info):
    while stack and stack[-1][0] <= prime_count:  # <= comparison
        stack.pop()
    # ...

2. Integer Overflow in Subsequence Count Calculation

The Pitfall: When calculating the number of valid subarrays for each element, the multiplication (index - left_bound) * (right_bound - index) can overflow for large arrays, even though Python handles big integers automatically. More importantly, developers might forget to handle the modulo operation correctly when raising to large powers.

Incorrect Approach:

# WRONG: Computing large power then taking modulo
result = (result * (value ** subsequence_count)) % MOD  # Can cause memory/time issues

Correct Approach:

# RIGHT: Using built-in modular exponentiation
result = result * pow(value, subsequence_count, MOD) % MOD

3. Edge Cases in Prime Factorization

The Pitfall: The prime factorization function might miss edge cases:

Not handling when n itself is prime after the loop
Not handling the case where n = 1 (though this shouldn't occur given "positive integers")
Using incorrect loop bounds (should be i * i <= n, not i <= n)

Common Mistake:

def count_distinct_prime_factors(n: int) -> int:
    i = 2
    distinct_factors = set()
  
    while i <= n:  # WRONG: Should be i * i <= n for efficiency
        while n % i == 0:
            distinct_factors.add(i)
            n //= i
        i += 1
  
    # MISSING: Not checking if n > 1 after the loop
    return len(distinct_factors)

Correct Implementation:

def count_distinct_prime_factors(n: int) -> int:
    i = 2
    distinct_factors = set()
  
    while i * i <= n:  # Correct bound
        while n % i == 0:
            distinct_factors.add(i)
            n //= i
        i += 1
  
    if n > 1:  # Important: n itself might be a prime factor
        distinct_factors.add(n)
  
    return len(distinct_factors)

4. Misunderstanding the Subarray Selection Rule

The Pitfall: Developers might misinterpret "each subarray can only be selected once" and incorrectly calculate the contribution of each element. The key insight is that an element can contribute to multiple different subarrays, and we need to count all valid subarrays where it has the maximum prime score.

Solution: Ensure you understand that:

Each element's contribution is based on ALL subarrays where it's the maximum (by prime score)
The count is (i - left[i]) × (right[i] - i) representing all possible combinations
We're not selecting k different elements, but rather using elements up to k times total

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don't know