Find the minimum possible sum of a beautiful array

Math Greedy

35.2% acceptance

Feb 25, 2026

317

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.

Solution

Rust

Time O(1)

Space O(1)

LeetCode

solution.rs

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;
    // Pick 1..floor(target/2), then target, target+1, ...
    let m = n.min(target / 2);
    let remaining = n - m;
    let sum_first = m * (m + 1) / 2 % MOD;
    let r = remaining % MOD;
    let r1 = if remaining > 0 { (remaining - 1) % MOD } else { 0 };
    let sum_rest = (r * (target % MOD) % MOD + r * r1 % MOD * 500_000_004 % MOD) % MOD;
    ((sum_first + sum_rest) % MOD) as i32
  }
}