LeetCode 2834. Find the Minimum Possible Sum of a Beautiful Array Solution in Java, C++, Python & More | Explanation + Code

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 + Mathematics

We can greedily construct the array nums starting from x = 1, choosing x each time and excluding target - x.

Let's denote m = \left\lfloor ^target⁄₂ \right\rfloor.

If x <= m, then the numbers we can choose are 1, 2, …, n, so the sum of the array is \left\lfloor ⁽¹⁺ⁿ⁾ⁿ⁄₂ \right\rfloor.

If x > m, then the numbers we can choose are 1, 2, …, m, a total of m numbers, and n - m numbers starting from target, so the sum of the array is \left\lfloor ^(1+m)m⁄₂ \right\rfloor + \left\lfloor ^{(target + target + n - m - 1)(n-m)}⁄₂ \right\rfloor.

Note that we need to take the modulus of 10⁹ + 7 for the result.

The time complexity is O(1), and the space complexity is O(1).

PythonJavaC++GoTypeScriptRustC#

class Solution: def minimumPossibleSum(self, n: int, target: int) -> int: mod = 10**9 + 7 m = target // 2 if n <= m: return ((1 + n) * n // 2) % mod return ((1 + m) * m // 2 + (target + target + n - m - 1) * (n - m) // 2) % mod(code-box)

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

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

func minimumPossibleSum(n int, target int) int { const mod int = 1e9 + 7 m := target / 2 if n <= m { return (n + 1) * n / 2 % mod } a := (m + 1) * m / 2 % mod b := (target + target + n - m - 1) * (n - m) / 2 % mod return (a + b) % mod }(code-box)

function minimumPossibleSum(n: number, target: number): number { const mod = 10 ** 9 + 7; const m = target >> 1; if (n <= m) { return (((1 + n) * n) / 2) % mod; } return (((1 + m) * m) / 2 + ((target + target + n - m - 1) * (n - m)) / 2) % mod; }(code-box)

impl Solution { pub fn minimum_possible_sum(n: i32, target: i32) -> i32 { const MOD: i64 = 1_000_000_007; let n = n as i64; let target = target as i64; let m = target / 2; if n <= m { return ((1 + n) * n / 2 % MOD) as i32; } let a = (1 + m) * m / 2 % MOD; let b = (target + target + n - m - 1) * (n - m) / 2 % MOD; ((a + b) % MOD) as i32 } }(code-box)

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