Get started

Determine the Minimum Sum of a k-avoiding Array — Medium Problem & Solution

An array of distinct positive integers is k-avoiding if no two different elements sum to k. Return the minimum possible sum of a k-avoiding array of length n.

  • Difficulty: Medium
  • Topics: Arrays, Math, Greedy
  • Asked at: Amazon, Google, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An array of distinct positive integers is k-avoiding if no two different elements sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1

Input: n = 5, k = 4
Output: 18
Explanation: `[1,2,4,5,6]` — 3 is skipped because `1 + 3 = 4`.

Example 2

Input: n = 2, k = 6
Output: 3
Explanation: `[1,2]` sums to 3 and avoids 6.

Example 3

Input: n = 1, k = 1
Output: 1

Constraints

  • 1 <= n, k <= 50

How to solve Determine the Minimum Sum of a k-avoiding Array

Greedily take 1, 2, 3, …, skipping any v whose partner k - v is already in the array. Stop once n numbers have been taken.

Approach

  1. Keep a set of chosen numbers and walk v upward from 1.
  2. Take v when k - v is not already chosen.
  3. Stop after n numbers and return their sum.

Why it works

Taking the smallest available number is safe because the numbers it blocks are all larger than it, so no cheaper option is ever lost. The pattern this produces is 1 … ⌊(k-1)/2⌋ followed by k, k+1, … — every pair inside the first block sums to less than k, and every number from k upward has a partner that is zero or negative.

Complexity

  • Time — O(n + k)
  • Space — O(n)

Pitfalls

  • The two elements of a forbidden pair must be different, so k being even does not rule out k/2 on its own.
  • Numbers at or above k are never blocked.
  • The array must hold exactly n distinct numbers.

Reference solution

Python

def minimumSum(n: int, k: int) -> int:
    used = set()
    total = 0
    v = 1
    while len(used) < n:
        if k - v not in used:
            used.add(v)
            total += v
        v += 1
    return total

JavaScript

var minimumSum = function(n, k) {
    var used = {};
    var sum = 0, v = 1, taken = 0;
    while (taken < n) {
        if (!used["" + (k - v)]) {
            used["" + v] = true;
            sum += v;
            taken++;
        }
        v++;
    }
    return sum;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue