Find the Minimum Possible Sum of a Beautiful Array

Find the Minimum Possible Sum of a Beautiful Array - Problem

Math Greedy Medium

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⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 4, target = 6

› Output: 12

💡 Note: One beautiful array is [1,3,4,6]. The pairs are (1,3), (1,4), (1,6), (3,4), (3,6) and (4,6). None sum to 6, so minimum sum is 1+3+4+6 = 14. But [1,2,4,7] gives 1+2+4+7 = 14, and [1,2,3,6] gives 1+2+3+6 = 12 which is smaller.

Example 2 — Small Target

$ Input: n = 2, target = 3

› Output: 4

💡 Note: We need 2 distinct numbers where no pair sums to 3. We can take [1,3] since 1+3=4≠3, giving sum 4. Or [2,3] since 2+3=5≠3, but [1,3] has smaller sum.

Example 3 — Large Array

$ Input: n = 3, target = 3

› Output: 8

💡 Note: Target is 3, so 1+2=3 is forbidden. We can take [1,3,4] but 1+2=3 so we can't take 2. Best is [1,3,4] giving sum 8.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ target ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

n=4 numbers needed, target=6 (forbidden sum)

Strategy

Greedily pick smallest numbers, avoid pairs summing to 6

Output

Beautiful array [1,2,3,6] with minimum sum 12

Key Takeaway

🎯 Key Insight: Greedily select smallest numbers while avoiding pairs that sum to target

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to greedily select the smallest available numbers while avoiding pairs that sum to target. The optimal approach uses mathematical analysis: take numbers 1 to target/2, then skip the forbidden range and continue from target. Best approach is mathematical formula. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(1)	O(1)	Calculate the sum directly using mathematical analysis
Brute Force with Set Generation	O(∞)	O(n)	Generate all possible arrays and find the one with minimum sum
Greedy Selection	O(n)	O(n)	Greedily pick the smallest numbers while avoiding forbidden pairs

Mathematical Formula — Algorithm Steps

Calculate how many numbers we can take from [1, t/2]
If we need more numbers, skip the forbidden range and continue from t
Use arithmetic series formula to compute sums efficiently
Apply modular arithmetic

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Pattern

Numbers 1 to target/2 are safe to take

Skip Forbidden

Skip numbers that would form pairs summing to target

Formula

Use arithmetic series to calculate sum directly

Code -

solution.c — C

#include <stdio.h>

int solution(int n, int target) {
    const int MOD = 1000000007;
    
    int half = target / 2;
    
    if (n <= half) {
        return ((long long) n * (n + 1) / 2) % MOD;
    } else {
        long long sum1 = ((long long) half * (half + 1) / 2) % MOD;
        int remaining = n - half;
        int start = target;
        int end = target + remaining - 1;
        long long sum2 = ((long long) remaining * (start + end) / 2) % MOD;
        
        return (sum1 + sum2) % MOD;
    }
}

int main() {
    int n, target;
    scanf("%d", &n);
    scanf("%d", &target);
    printf("%d\n", solution(n, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Direct mathematical calculation with constant time operations

✓ Linear Growth

Space Complexity

O(1)

Only a few variables needed for calculation

✓ Linear Space

8.6K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler