Welcome to Subscribe On Youtube

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.

  • 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;
        }
    }
    
  • 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;
        }
    };
    
  • 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
    
    
  • 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
    }
    
  • 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;
    }
    
    

All Problems

All Solutions