2834. Find the minimum sum of a beautiful array

Problem: 2834. Find the minimum sum of a beautiful array

Question description

Given two positive integers n and target, the goal is to find a length of n array that satisfies the following conditions:

• An array consists of two different positive integers.
• There are no two different subscripts i and j make nums[i] + nums[j] == target。
  Returns the smallest possible sum of a beautiful array that meets the conditions, and performs the 10^9 + 7 Take the mold.

test case

Example 1:

• Input: n = 2, target = 3
• Output: 4

Example 2:

• Input: n = 3, target = 3
• Output: 8

Example 3:

• Input: n = 1, target = 1
• Output: 1

Original idea

Plan

The initial solution is to start with the smallest number and check each number one by one whether it can be added to the array, while ensuring that there are no two numbers whose sum is equal to target。

• from 1 Start trying to add numbers to the array one by one.
• For each number, check if adding it to a number already in the array gives target。
• If not, add it to the array.
• Continue this process until the array length reaches n。

code

1
2
3
4
5
6
7
8
9
10
11
12

def minimumPossibleSum(n, target):
    selected_nums = set([1])
    total_sum = 1
    current_num = 2

    while len(selected_nums) < n:
        if all((current_num + num != target) for num in selected_nums):
            selected_nums.add(current_num)
            total_sum += current_num
        current_num += 1

    return total_sum % (10**9 + 7)

Complexity analysis

• Time complexity: O(n^2), because the addition of each number requires traversing the selected number set.
• Space complexity: O(n) for storing the selected set of numbers.

greedy optimization

Plan

• Optimization strategy：

  • Avoid the use of collections：
    • Introduce the "avoid" collection to store all the results obtained by adding the selected number target number.
    • This allows a quick check to see if the new number will result in a sum of target situation.
  • direct inspection：
    • Each time a new number is selected, only check if it is in the "avoid" set.
    • Numbers not in the set are considered safe and can be added directly.
  • Dynamic update avoid collection：
    • When new numbers are added to the beautiful array, the corresponding target - 新数字 Also added to the "Avoid" collection.
    • This ensures that any possible composition with new numbers target numbers will be avoided in the future.

• Optimized time complexity：

  • Only one set check is required per number.
  • The time complexity is reduced to O(n), which significantly improves the algorithm efficiency.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def minimumPossibleSum_optimized(n, target):
    selected_nums = set()
    avoid_nums = set()
    total_sum = 0
    current_num = 1

    while len(selected_nums) < n:
        if current_num not in avoid_nums:
            selected_nums.add(current_num)
            total_sum += current_num
            avoid_nums.add(target - current_num)
        current_num += 1

    return total_sum % (10**9 + 7)

Complexity analysis

• Time complexity: O(n) since each number only needs to be checked once.
• Space complexity: O(n) for storing selected numbers and avoiding collections of numbers.

mathematical methods

Plan

In response to the above problems, we adopted a more efficient mathematical method to solve this problem. This method reduces the necessary amount of calculations by analyzing the mathematical nature of the problem, and is particularly suitable for processing large-scale data.

1. Problem decomposition：

   • First, we break the problem into two parts. Since the numbers in the array are all unique, and the sum of two different numbers cannot be equal to target, we select first starting with the smallest number until we can no longer select any more numbers without violating the rules of sum.

2. Select the first half of the number：

   • in 1 Arrive target-1 Within the range, some numbers cannot appear at the same time. For example, if target Yes 6, then 1 and 5、2 and 4 cannot occur at the same time because their sum is equal to 6. However,3(when target is an even number) or 3 and 2(when target is an odd number) can be selected.
   • This means we are free to choose from 1 Arrive m of numbers, among which m = min(⌊target/2⌋, n). For this part of the numbers, we can directly use the summation formula of the arithmetic sequence to calculate their sum, that is m * (m + 1) / 2。

3. Select the second half of the number：

   • Once we select the former m numbers, the remaining number that needs to be selected is n - m. Since we have chosen 1 Arrive m, we now need to start from target Start selecting the remaining numbers.
   • if n greater than m, then we will start from target Start continuous selection n - m number. The sum of these numbers can be calculated using the summation formula of an arithmetic sequence:(2 * target + n - m - 1) * (n - m) / 2。

4. Calculate the sum and take the modulo：

   • We add the sum of the two parts and do the 10^9 + 7 Take modulo to get the final answer.

realize

• First part sum: from 1 Arrive min(target // 2, n) of and.
• Second part and (if required): from target start, choose n - min(target // 2, n) sum of numbers.
• Add the sums of these two parts to get the minimum sum of a beautiful array that meets the conditions.

1. Select less than target // 2 number：

   • As we start from 1 and gradually increase the number until target // 2, these numbers cannot be added to other numbers in the array to get target。
   • For example, if target is 10, then target // 2 Yes 5. In this case, any two numbers between 1 and 5 will never add up to 10.
   • Therefore, this part of the selection is safe, and since we need the minimum sum, we start from 1 and increase one by one.

2. **When n greater than target // 2**：

   • if n greater than target // 2, which means only select less than target // 2 There are not enough numbers to fill the array.
   • In this case we need to keep selecting more numbers, but to avoid and for target The combination of we need from target Start choosing yourself.
   • We continue to increase one by one until the array length reaches n。

3. Calculate the sum：

   • The first part is from 1 to min(target // 2, n) of and.
   • The second part (if needed) is from target Go ahead and choose the rest n - min(target // 2, n) number.
   • Finally, adding the sum of these two parts is the minimum sum we are looking for.

This is a typical example of solving problems through mathematical methods, which avoids complex programming logic and provides a more concise and efficient solution.

code

1
2
3
4
5
6
7

def minimumPossibleSum_math_approach(n, target):
    MOD = 10**9 + 7
    m = min(target // 2, n)
    first_half_sum = m * (m + 1) // 2
    remaining = n - m
    second_half_sum = (2 * target + remaining - 1) * remaining // 2
    return (first_half_sum + second_half_sum) % MOD

Complexity analysis

• Time complexity: O(1) since the result is calculated directly.
• Space complexity: O(1), only a fixed number of variables are used.