Problem

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 _theminimum possible sum that a beautiful array could have modulo _10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7

Input: n = 2, target = 3
Output: 4
Explanation: We can see that nums = [1,3] is beautiful.
- The array nums has length n = 2.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 4 is the minimum possible sum that a beautiful array could have.

Example 2

1
2
3
4
5
6
7

Input: n = 3, target = 3
Output: 8
Explanation: We can see that nums = [1,3,4] is beautiful.
- The array nums has length n = 3.
- The array nums consists of pairwise distinct positive integers.
- There doesn't exist two distinct indices, i and j, with nums[i] + nums[j] == 3.
It can be proven that 8 is the minimum possible sum that a beautiful array could have.

Example 3

1
2
3

Input: n = 1, target = 1
Output: 1
Explanation: We can see, that nums = [1] is beautiful.

Constraints

  • 1 <= n <= 10^9
  • 1 <= target <= 10^9

Solution

Method 1 – Greedy Construction

Intuition

To minimize the sum, pick the smallest possible distinct positive integers, but avoid pairs that sum to target. The best way is to pick numbers from 1 upwards, skipping any number that would form a forbidden pair with a previously chosen number.

Approach

  1. Initialize an empty set to track chosen numbers and a variable for the sum.
  2. Iterate from 1 upwards, for each number:
    • If target - x is not already chosen, pick x.
    • Add x to the sum and the set.
    • Stop when n numbers are chosen.
  3. Return the sum modulo 10^9 + 7.

Code

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

class Solution {
public:
    int minimumPossibleSum(int n, int target) {
        const int MOD = 1e9+7;
        set<int> used;
        long long sum = 0;
        for(int x=1, cnt=0; cnt<n; ++x) {
            if(used.count(target-x)) continue;
            sum = (sum + x) % MOD;
            used.insert(x);
            ++cnt;
        }
        return sum;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func minimumPossibleSum(n int, target int) int {
    const MOD = 1_000_000_007
    used := make(map[int]bool)
    sum, cnt := 0, 0
    for x := 1; cnt < n; x++ {
        if used[target-x] { continue }
        sum = (sum + x) % MOD
        used[x] = true
        cnt++
    }
    return sum
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minimumPossibleSum(int n, int target) {
        final int MOD = 1_000_000_007;
        Set<Integer> used = new HashSet<>();
        long sum = 0;
        for(int x=1, cnt=0; cnt<n; ++x) {
            if(used.contains(target-x)) continue;
            sum = (sum + x) % MOD;
            used.add(x);
            ++cnt;
        }
        return (int)sum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minimumPossibleSum(n: Int, target: Int): Int {
        val MOD = 1_000_000_007
        val used = mutableSetOf<Int>()
        var sum = 0L; var cnt = 0
        var x = 1
        while (cnt < n) {
            if ((target-x) in used) { x++; continue }
            sum = (sum + x) % MOD
            used.add(x)
            cnt++
            x++
        }
        return sum.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        MOD = 10**9+7
        used = set()
        ans = 0
        x = 1
        while n:
            if target-x not in used:
                ans = (ans + x) % MOD
                used.add(x)
                n -= 1
            x += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn minimum_possible_sum(n: i32, target: i32) -> i32 {
        let mut used = std::collections::HashSet::new();
        let mut sum = 0i64;
        let mut cnt = 0;
        let mut x = 1;
        while cnt < n {
            if !used.contains(&(target-x)) {
                sum = (sum + x as i64) % 1_000_000_007;
                used.insert(x);
                cnt += 1;
            }
            x += 1;
        }
        sum as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    minimumPossibleSum(n: number, target: number): number {
        const MOD = 1_000_000_007;
        const used = new Set<number>();
        let sum = 0, cnt = 0, x = 1;
        while(cnt < n) {
            if(!used.has(target-x)) {
                sum = (sum + x) % MOD;
                used.add(x);
                cnt++;
            }
            x++;
        }
        return sum;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we pick n numbers.
  • 🧺 Space complexity: O(n), for the set of used numbers