Scale Engineer

Find the Minimum Possible Sum of a Beautiful Array

Med
#2534Time: O(n + target). In the worst-case scenario, the loop might run up to `n + target/2` times to find `n` valid numbers. Given the constraints, this approach is too slow and will time out.Space: O(n). The `HashSet` will store up to `n` elements. Given `n` can be as large as 10<sup>9</sup>, this will lead to a Memory Limit Exceeded error.1 company
Patterns
MathGreedy
Companies
Infosys

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of building the beautiful array. The core idea is to construct the array greedily to ensure the sum is minimized. To do this, we iterate through positive integers starting from 1 and add them to our array if they do not violate the 'beautiful' condition. The condition is that for any two numbers x and y in the array, x + y != target. This means if we add a number num, we cannot add target - num later. A HashSet is used to keep track of the numbers already included in our array for efficient lookups.

Algorithm

  • Initialize sum = 0, count = 0, num = 1, and a HashSet named seen.
  • Loop until n numbers are found (i.e., count == n).
  • In each iteration, check if target - num is already present in the seen set.
  • If it is not present, it means adding num will not violate the beautiful array condition. So, add num to the sum and to the seen set, and then increment count.
  • Increment num in every iteration to consider the next integer.
  • After the loop finishes, return the total sum.

Walkthrough

To achieve the minimum possible sum, our strategy should be to select the smallest possible distinct positive integers. We can iterate through integers num = 1, 2, 3, ... and decide whether to include them in our array.

A number num can be included if, for all existing numbers x in our array, num + x != target. This is equivalent to checking if target - num is already in our array. We can use a HashSet to store the numbers we've chosen, allowing for an average O(1) time complexity for this check.

We continue this process, adding the smallest valid integers, until we have collected n numbers. The sum is accumulated along the way, with modulo operations to prevent overflow.

import java.util.HashSet; class Solution {    public int minimumPossibleSum(int n, int target) {        HashSet<Integer> seen = new HashSet<>();        long sum = 0;        int count = 0;        int num = 1;        long MOD = 1_000_000_007;         while (count < n) {            if (!seen.contains(target - num)) {                sum = (sum + num);                seen.add(num);                count++;            }            num++;        }        return (int)(sum % MOD);    }}

This code snippet implements the greedy strategy. However, since n can be up to 10<sup>9</sup>, a loop that depends on n will be too slow.

Complexity

Time

O(n + target). In the worst-case scenario, the loop might run up to `n + target/2` times to find `n` valid numbers. Given the constraints, this approach is too slow and will time out.

Space

O(n). The `HashSet` will store up to `n` elements. Given `n` can be as large as 10<sup>9</sup>, this will lead to a Memory Limit Exceeded error.

Trade-offs

Pros

  • The logic is straightforward and easy to understand.

  • It correctly models the greedy choice of picking the smallest available numbers.

Cons

  • Highly inefficient for large values of n and target due to its linear time and space complexity relative to n.

  • Will result in a Time Limit Exceeded (TLE) error for the given constraints.

  • Will result in a Memory Limit Exceeded (MLE) error for the given constraints.

Solutions

public class Solution {    public int MinimumPossibleSum(int n, int target) {        const int mod = (int) 1 e9 + 7;        int m = target / 2;        if (n <= m) {            return (int)((1 L + n) * n / 2 % mod);        }        long a = (1 L + m) * m / 2 % mod;        long b = ((1 L * target + target + n - m - 1) * (n - m) / 2) % mod;        return (int)((a + b) % mod);    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem