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

Append K Integers With Minimal Sum

Number: 2305

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums and an integer k, append k unique positive integers that do not appear in nums such that the sum of the k appended numbers is minimized. Return the sum of these appended integers.

Key Insights

  • The smallest numbers yield the minimal sum; therefore, consider positive integers starting from 1.
  • Avoid numbers already present in nums.
  • Sorting the unique values in nums helps identify “gaps” where missing numbers can be efficiently selected.
  • Instead of iterating one by one (which can be inefficient for large k), use arithmetic sum formulas for consecutively missing numbers.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the unique values from nums.
Space Complexity: O(n) for storing the unique numbers.

Solution

  1. Convert nums to a set and then to a sorted list to eliminate duplicates and process in order.
  2. Initialize a candidate variable to 1.
  3. Iterate over each number in the sorted list:
    • For each number, if there is a gap between the candidate and the current number, determine how many missing numbers can be picked from the gap.
    • If the gap contains more missing integers than needed (k remains), use the arithmetic series formula to add the sum of the required count and update candidate accordingly.
    • Otherwise, add the entire gap, subtract the count from k, and move the candidate past the current number.
  4. After processing the sorted nums, if k is still positive, add the k consecutive integers starting from candidate using the arithmetic series formula.
  5. Return the computed sum.

Code Solutions

# Python solution
def minimalKSum(nums, k):
    # Remove duplicates and sort the numbers
    unique_nums = sorted(set(nums))
    result = 0
    current = 1

    for num in unique_nums:
        if current < num:
            # Calculate number of missing integers between current and num-1
            gap = num - current
            if k <= gap:
                # Add the sum of k consecutive integers starting from current
                result += (current + current + k - 1) * k // 2
                k = 0
                break
            else:
                # Add entire gap sum
                result += (current + num - 1) * gap // 2
                k -= gap
        # Move candidate to the next integer after num
        current = max(current, num + 1)

    # If k numbers are still needed, add them starting from current
    if k > 0:
        result += (current + current + k - 1) * k // 2

    return result

# Example usage:
print(minimalKSum([1,4,25,10,25], 2))  # Output: 5
← Back to All Questions