Tejav
#2834

Find the Minimum Possible Sum of a Beautiful Array

Medium
MathGreedyGreedySet
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages the fact that we can directly calculate the minimum sum by avoiding numbers that could create pairs summing to the target. By carefully selecting the smallest distinct integers, we ensure the array remains beautiful.

⚙️

Algorithm

3 steps
  1. 1Step 1: Initialize an empty set to track used numbers and a variable for total_sum.
  2. 2Step 2: Iterate through integers starting from 1, adding them to the total_sum if they do not create a pair with any previously added number that sums to the target.
  3. 3Step 3: Stop when we have added n distinct integers, and return the total_sum modulo 10^9 + 7.
solution.py12 lines
1# Full working Python code
2
3def min_beautiful_sum(n, target):
4    total_sum = 0
5    used = set()
6    for i in range(1, n + target):
7        if i not in used and (target - i) not in used:
8            used.add(i)
9            total_sum += i
10            if len(used) == n:
11                break
12    return total_sum % (10**9 + 7)
ℹ

Complexity note: The time complexity is O(n) because we only iterate through the integers until we reach n distinct numbers, and we check for pairs in constant time using a set.

  • 1Greedily select the smallest numbers to minimize the sum.
  • 2Avoid pairs that sum to the target by tracking used numbers.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.