Maximize Score based Prime Score Algorithm

Question

Consider the following LeetCode problem:

You are given an array nums of n positive integers and an integer k. Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:

Choose any non-empty subarray nums\[l, ..., r\] that you haven't chosen previously.

Choose an element x of nums\[l, ..., r\] with the highest prime score. If multiple such elements exist, choose the one with the smallest index.

Multiply your score by x. Here, nums\[l, ..., r\] denotes the subarray of nums starting at index l and ending at the index r, both ends being inclusive.

The prime score of an integer x is equal to the number of distinct prime factors of x. For example, the prime score of 300 is 3 since 300 = 2 * 2 * 3 * 5 * 5.

Return the maximum possible score after applying at most k operations.

Since the answer may be large, return it modulo 10^9 + 7.

Now consider the following case:

\[3289,2832,14858,22011\] k = 6

Now, I just need to know the AMOUNT of subarrays. A formula to calculate amount of subarrays that includes the element at index i is the following:

Number of Subarrays = (r + 1) * (l + 1) Where l is how far to the left I can move from i Where r is how far to the right I can move from r

Now the largest element is 22011, so we can consider \[22011\]. 22011 has a prime score of 4. We CANNOT use 22011 in \[14858, 22011\] because 14858 also has a prime score of 4 and we need to use the leftmost index if it is a tie. So r = 0 because we can't move right (it's the last element) and we also can't move left (l = 0). So the number of subarrays is 1, so we only use 220111 once.

Now the next largest element is 14858. In this case r = 1 and l = 2. Because 22011 and 14858 have the same prime score and we use the leftmost index and 14858 has a greater prime score of the preceding 2 elements, so the amount of subarrays is (2 + 1)*(1+1) = 6. Now since we already used 22011 once, we can only multiply 14858 five times since k = 6. So the final answer would be

(22011 * 14858 * 14858 * 14858 * 14858 * 14858) MOD ((10^9) +7) This gives us: 719826932

But the right answer (according to LeetCode) is

which is 256720975

Can anyone explain what I am doing wrong? LeetCode's solution uses a montonic stack, but I want to see if my way also works.

Please take a look at the displayed form of your question, then edit it to remove the extraneous backslashes. — President James K. Polk
– President James K. Polk, Commented Nov 3 at 18:39
You've got a floating point or other precision problem on your hands. Put (22011 * 14858 * 14858 * 14858 * 14858 * 14858) % (10**9 + 7) in a Python repl and you get 256720975. — Welbog
– Welbog, Commented Nov 4 at 1:50

trincot · Accepted Answer · 2025-11-04 09:00:34Z

"This gives us: 719826932": This wrong result seems to suggest you are using a floating point data type for your calculations. For instance in JavaScript this a problem you get with the "number" type. In that case the product can get a magnitude that cannot be correctly represented with its floating point data type.

To solve this, either:

perform the remainder operation after each individual multiplication before continuing with a next multiplication; or
use an integer type that can be dynamic in size, like JavaScript's BigInt, or Python's int type.

Here is a JavaScript snippet that performs your example calculation in both ways:

function method_float() { const mod = 1e9 + 7; const numbers = [22011, 14858, 14858, 14858, 14858, 14858]; let product = 1; // Apply remainder operation after each multiplication: for (const num of numbers) product = (product * num) % mod; console.log(product); } function method_bigint() { // Use BigInt data type for all calculations const mod = 10n**9n + 7n; const bigints = [22011n, 14858n, 14858n, 14858n, 14858n, 14858n]; let product = 1n; for (const num of bigints) product *= num; console.log(Number(product % mod)); } method_float(); method_bigint();

Collectives™ on Stack Overflow

Maximize Score based Prime Score Algorithm

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related