REDONE - Editorial

editorial
,
1

Problem Link - Reduce to One Practice Problem in 1400 to 1600 difficulty problems

Problem Statement:

Given a list of integers from 1 to N, you repeatedly perform the operation:

  1. Choose two elements X and Y from the list (they can be equal).
  2. Replace them with the number X+Y+X⋅Y.

The goal is to find the maximum possible final number that remains in the list after performing this operation N−1 times, and then return the result modulo 10^9 + 7.

Approach:

This is essentially computing: (n+1)! −1 mod (10^9 + 7)

Precomputation of Factorials Modulo 10^9 + 7:

  • To solve this problem efficiently, instead of computing the factorial for each test case individually (which can be slow), we precompute the factorials modulo 10^9 + 7 up to a maximum number (in this case 10^6 + 1).
  • This is stored in the array preCompute, where preCompute[i] holds i! mod (10^9 + 7).

Factorial Computation:

  • We initialize the first factorial preCompute[1] = 1 (since 1!=1).
  • Then, for each number from 2 to maxN - 1 (which is 10^6 + 1), we calculate the factorial of the current number iteratively: preCompute[i]=(preCompute[i−1]×i) mod(10^9+7)
  • This ensures that all factorials up to 10^6 + 1 are computed efficiently using previously computed values.

Handling Multiple Test Cases:

  • After precomputing the factorial values, for each test case, we directly retrieve the factorial of n+1 from the preCompute array.
  • The result is computed by subtracting 1 from (n+1)!mod (10^9+7), then outputting the result modulo 10^9 + 7.

Complexity:

  • Time Complexity: Computing the factorial for all numbers from 1 to 10^6+1 takes O(maxN), where maxN=10^6+2. Since each computation involves a constant number of operations (multiplication and modulo), this is efficient.
  • Space Complexity: We use an array of size maxN to store the factorials. Thus, the space complexity is O(maxN).