Determine the Minimum Sum of a k-avoiding Array

Medium
997.

Determine the Minimum Sum of a k-avoiding Array

Determine the Minimum Sum of a k-avoiding Array is a medium coding problem on arrays, math and greedy, asked in Amazon, Google and Oracle interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var minimumSum = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Determine the Minimum Sum of a k-avoiding Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Determine the Minimum Sum of a k-avoiding Array is a medium coding problem on arrays, math and greedy, asked in Amazon, Google and Oracle interviews.

  • 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

Hints for Determine the Minimum Sum of a k-avoiding Array

  1. Hint 1

    Take the smallest numbers you can, in order.

  2. Hint 2

    A number v is blocked only if k - v has already been taken.

  3. Hint 3

    Once past k, nothing is ever blocked again.

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

Java

public static int minimumSum(int n, int k) {
    Set<Integer> used = new HashSet<>();
    int sum = 0, v = 1;
    while (used.size() < n) {
        if (!used.contains(k - v)) {
            used.add(v);
            sum += v;
        }
        v++;
    }
    return sum;
}

C++

int minimumSum(int n, int k) {
    unordered_set<int> used;
    int sum = 0, v = 1;
    while ((int) used.size() < n) {
        if (used.find(k - v) == used.end()) {
            used.insert(v);
            sum += v;
        }
        v++;
    }
    return sum;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms