We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Find the Minimum Possible Sum of a Beautiful Array

Difficulty: Medium

Problem Description

You are given positive integers n and target. An array nums is beautiful if it meets the following conditions:

nums.length == n.
nums consists of pairwise distinct positive integers.
There doesn't exist two distinct indices, i and j, in the range [0, n - 1], such that nums[i] + nums[j] == target.

Return the minimum possible sum that a beautiful array could have modulo 10^9 + 7.

Key Insights

The elements of the array must be distinct positive integers.
The sum of any two distinct integers in the array should not equal the target.
To minimize the sum, we should start with the smallest integers and skip any integers that would create a sum of target.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a greedy approach:

Start with the smallest positive integers (1, 2, 3, ...).
Keep adding integers to the array until we reach the required length n.
If adding an integer x would cause a pair (x, target - x) to be formed in the array, skip it.
Continue this process until we have n valid integers.
Calculate the sum of these integers and return it modulo 10^9 + 7.

This approach ensures that we find the minimum sum while adhering to the constraints of the problem.

Code Solutions

def minSumBeautifulArray(n, target):
    MOD = 10**9 + 7
    total_sum = 0
    used = set()
    
    for i in range(1, n + 1):
        if (target - i) not in used:
            total_sum += i
            used.add(i)
    
    return total_sum % MOD

← Back to All Questions