2834. Find the Minimum Possible Sum of a Beautiful Array

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

 

Example 1:

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:

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:

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

 

Constraints:

  • 1 <= n <= 109
  • 1 <= target <= 109

Solutions

Solution 1: Greedy + Hash Table

We start from the positive integer $i=1$, and judge whether $i$ can be added to the array in turn. If it can be added, we add $i$ to the array, accumulate it to the answer, and then mark $target-i$ as visited, indicating that $target-i$ cannot be added to the array. The loop continues until the length of the array is $n$.

The time complexity is $O(n + target)$, and the space complexity is $O(n + target)$. Here, $n$ is the length of the array.

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

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        vis = set()
        ans = 0
        i = 1
        for _ in range(n):
            while i in vis:
                i += 1
            ans += i
            vis.add(target - i)
            i += 1
        return ans

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

class Solution {
    public long minimumPossibleSum(int n, int target) {
        boolean[] vis = new boolean[n + target];
        long ans = 0;
        for (int i = 1; n > 0; --n, ++i) {
            while (vis[i]) {
                ++i;
            }
            ans += i;
            if (target >= i) {
                vis[target - i] = true;
            }
        }
        return ans;
    }
}

C++ Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    long long minimumPossibleSum(int n, int target) {
        bool vis[n + target];
        memset(vis, false, sizeof(vis));
        long long ans = 0;
        for (int i = 1; n; ++i, --n) {
            while (vis[i]) {
                ++i;
            }
            ans += i;
            if (target >= i) {
                vis[target - i] = true;
            }
        }
        return ans;
    }
};

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

func minimumPossibleSum(n int, target int) (ans int64) {
	vis := make([]bool, n+target)
	for i := 1; n > 0; i, n = i+1, n-1 {
		for vis[i] {
			i++
		}
		ans += int64(i)
		if target >= i {
			vis[target-i] = true
		}
	}
	return
}

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

function minimumPossibleSum(n: number, target: number): number {
    const vis: boolean[] = Array(n + target).fill(false);
    let ans = 0;
    for (let i = 1; n; ++i, --n) {
        while (vis[i]) {
            ++i;
        }
        ans += i;
        if (target >= i) {
            vis[target - i] = true;
        }
    }
    return ans;
}