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 109, this will lead to a Memory Limit Exceeded error.1 company

Patterns

Math Greedy

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 10⁹ + 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 <= 10⁹
1 <= target <= 10⁹

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.

1import java.util.HashSet;2 3class Solution {4    public int minimumPossibleSum(int n, int target) {5        HashSet<Integer> seen = new HashSet<>();6        long sum = 0;7        int count = 0;8        int num = 1;9        long MOD = 1_000_000_007;10 11        while (count < n) {12            if (!seen.contains(target - num)) {13                sum = (sum + num);14                seen.add(num);15                count++;16            }17            num++;18        }19        return (int)(sum % MOD);20    }21}

This code snippet implements the greedy strategy. However, since n can be up to 109, 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 109, 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.

By analyzing the greedy strategy from the first approach, we can observe a distinct pattern in the numbers that are selected. This pattern allows us to derive a direct mathematical formula to compute the sum without any iteration, leading to a highly efficient O(1) solution. This approach is necessary to pass the large constraints of the problem.

Algorithm

Calculate m = target / 2.
Case 1: n <= m
- The array will consist of the first n positive integers: 1, 2, ..., n.
- The sum is the sum of the first n natural numbers: sum = n * (n + 1) / 2.
Case 2: n > m
- The array is formed by two groups of numbers:
  1. The first m positive integers: 1, 2, ..., m.
  2. The next n - m numbers, starting from target: target, target + 1, ....
- Calculate the sum of the first part: sum1 = m * (m + 1) / 2.
- Calculate the sum of the second part, which is an arithmetic series of k = n - m terms: sum2 = k * target + k * (k - 1) / 2.
- The total sum is (sum1 % MOD + sum2 % MOD) % MOD.
Use long for all intermediate calculations to prevent integer overflow.

Walkthrough

The greedy strategy of picking the smallest available positive integer i as long as target - i is not already in our set leads to a predictable sequence of numbers.

For any integer i <= target / 2, its counterpart j = target - i is greater than or equal to i. Since we pick numbers in increasing order, when we consider i, j has not been considered yet, so we will always pick i. This means we select all integers from 1 to m = floor(target / 2).
For any integer i such that target / 2 < i < target, its counterpart j = target - i is smaller than i (i.e., j <= m). Since we have already picked all numbers up to m, j is already in our set. Therefore, we must skip all such i.
For any integer i >= target, its counterpart target - i is not a positive integer, so it cannot be in our set of chosen positive integers. Thus, we can pick any i >= target.

This means the set of available numbers for our beautiful array is {1, 2, ..., m} cup {target, target+1, ...}. To get the minimum sum, we take the n smallest numbers from this combined set.

This leads to two cases:

n <= m: We just need the first n numbers, which are 1, 2, ..., n. The sum is n * (n + 1) / 2.
n > m: We take all m numbers from 1 to m, and then we need k = n - m more numbers. The next smallest available numbers are target, target + 1, .... We take the first k numbers from this sequence. The total sum is the sum of these two arithmetic progressions.

This logic can be implemented with constant time complexity.

1class Solution {2    public int minimumPossibleSum(int n, int target) {3        long MOD = 1_000_000_007;4        long m = target / 2;5 6        if (n <= m) {7            long val = n;8            long sum = val * (val + 1) / 2;9            return (int) (sum % MOD);10        } else {11            // Sum of the first part: 1, 2, ..., m12            long sum1 = m * (m + 1) / 2;13 14            // Sum of the second part: k = n - m numbers starting from target15            long k = n - m;16            // Arithmetic series: k*a + k*(k-1)/217            long sum2 = k * target + k * (k - 1) / 2;18 19            long totalSum = (sum1 % MOD + sum2 % MOD) % MOD;20            return (int) totalSum;21        }22    }23}

Complexity

Time

O(1). The sum is calculated using a direct mathematical formula involving a few arithmetic operations, which take constant time.

Space

O(1). The solution uses only a few variables for calculation, irrespective of the input size.

Trade-offs

Pros

Extremely efficient, with constant time and space complexity.
Handles the large constraints on n and target effectively.
Provides a direct and elegant solution once the pattern is understood.

Cons

The derivation of the formula requires mathematical insight into the pattern, which might not be immediately obvious.

Solutions

Solution

1public class Solution {2    public int MinimumPossibleSum(int n, int target) {3        const int mod = (int) 1 e9 + 7;4        int m = target / 2;5        if (n <= m) {6            return (int)((1 L + n) * n / 2 % mod);7        }8        long a = (1 L + m) * m / 2 % mod;9        long b = ((1 L * target + target + n - m - 1) * (n - m) / 2) % mod;10        return (int)((a + b) % mod);11    }12}

1class Solution {2public3  long minimumPossibleSum(int n, int target) {4    boolean[] vis = new boolean[n + target];5    long ans = 0;6    for (int i = 1; n > 0; --n, ++i) {7      while (vis[i]) {8        ++i;9      }10      ans += i;11      if (target >= i) {12        vis[target - i] = true;13      }14    }15    return ans;16  }17}

1class Solution {2public:3  long long minimumPossibleSum(int n, int target) {4    bool vis[n + target];5    memset(vis, false, sizeof(vis));6    long long ans = 0;7    for (int i = 1; n; ++i, --n) {8      while (vis[i]) {9        ++i;10      }11      ans += i;12      if (target >= i) {13        vis[target - i] = true;14      }15    }16    return ans;17  }18};

1class Solution:2    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

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 problem