We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Possible Sum of a Beautiful Array

Number: 3026

Difficulty: Medium

Paid? No

Companies: Infosys

Problem Description

Given two positive integers n and target, construct an array nums of n pairwise distinct positive integers such that there do not exist two distinct indices i and j with nums[i] + nums[j] == target. We want to minimize the sum of nums (and return it modulo 10^9+7).

Key Insights

  • The “conflict” arises only when two numbers from the array sum to target.
  • In the range [1, target - 1] numbers naturally form pairs: (x, target - x). For each such pair (with x < target - x), only the smaller number is optimal to pick in order to minimize the overall sum.
  • For target even the midpoint (target/2) is self‐conflicting only if picked twice – so one copy is allowed.
  • The best strategy is to pick as many small “safe” numbers from 1 to target-1 (using only one number from each forbidden pair). If more numbers are needed, pick the next smallest numbers starting from target which are automatically safe.
  • Use arithmetic progression formulas to get the sum and apply modulo operations to keep numbers in range.

Space and Time Complexity

Time Complexity: O(1) – all operations use constant time mathematical calculations. Space Complexity: O(1) – only a fixed number of variables are used.

Solution

We first determine the set S of “safe” numbers that we can choose from the range [1, target-1] without conflict. For each pair (i, target-i) for i from 1 to floor((target-1)/2), choose i. Additionally, if target is even, include target/2 as a “center” number because one instance is allowed.

Let m = floor((target-1)/2) and extra = 1 if target is even (else 0). Then safeCount = m + extra.

Case 1: n ≤ safeCount
 – We can pick n numbers from S. Since S sorted starts with the smallest numbers, if n is entirely among the smallest ones (or in the case target is even, possibly including target/2 as the last element) the sum is computed accordingly.
  • For example, if target is odd, S = [1, 2, …, m] so answer = n*(n+1)/2.
  • For target even and if n equals m+1 (i.e. using all available safe elements), answer = (sum of 1 through m) + target/2.

Case 2: n > safeCount
 – Use all safe numbers S first, and then choose the additional k2 = n − safeCount numbers from starting at target. These additional numbers are consecutive: target, target+1, …, target+k2-1.  – Their sum is: k2target + k2(k2-1)/2.  – Final answer is the sum of S plus the additional sum (all taken modulo 10^9+7).

We use arithmetic progression formulas and careful modulo arithmetic to handle large numbers.

Code Solutions

# Python solution with line-by-line comments
MOD = 10**9 + 7
def min_beautiful_sum(n: int, target: int) -> int:
    # Calculate m = floor((target-1)/2)
    m = (target - 1) // 2
    # Determine if there is an extra center element for even target
    extra = 1 if target % 2 == 0 else 0
    safe_count = m + extra  # Maximum numbers we can pick from 1 to target-1 safely

    if n <= safe_count:
        # If we can pick all numbers from the safe set
        if target % 2 == 0 and n == m + 1:
            # Sum = sum of 1...m plus the center element (target/2)
            sum_first = m * (m + 1) // 2  # sum of first m numbers
            return (sum_first + target // 2) % MOD
        else:
            # In other cases safe set are simply the smallest n natural numbers.
            return (n * (n + 1) // 2) % MOD
    else:
        # Use all safe numbers from S
        if target % 2 == 0:
            # Safe set S: [1,2,..., m] and then target/2
            sum_S = (m * (m + 1) // 2 + target // 2) % MOD
        else:
            # For odd target, safe set S is [1,2,..., m]
            sum_S = (m * (m + 1) // 2) % MOD
        # Calculate how many additional numbers we need beyond S:
        k2 = n - safe_count
        # Sum of k2 consecutive numbers starting at target:
        additional_sum = (k2 * target + (k2 * (k2 - 1) // 2)) % MOD
        return (sum_S + additional_sum) % MOD

# Example usage:
print(min_beautiful_sum(2, 3))  # Expected output: 4
print(min_beautiful_sum(3, 3))  # Expected output: 8
print(min_beautiful_sum(1, 1))  # Expected output: 1
← Back to All Questions