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

Apply Operations to Make Sum of Array Greater Than or Equal to k

Number: 3328

Difficulty: Medium

Paid? No

Companies: Turing, ZScaler

Problem Description

You start with an array nums = [1] and are allowed to perform two types of operations any number of times:

  1. Increase any element of the array by 1.
  2. Duplicate any element (i.e., append a copy of it) to the array. Given a positive integer k, the goal is to make the sum of the array greater than or equal to k using the minimum number of operations.

Key Insights

  • The two operations (increment and duplicate) are independent. Increments increase the value contained in an element while duplication multiplies the number of copies.
  • If you increase the only element from 1 to x (which costs x-1 operations), then duplicating it d times produces an array with d+1 elements of value x, and the total sum becomes x*(d+1).
  • The task is then to choose an integer x (after performing x - 1 increments) and a number c (where c = number of copies = d+1, hence d = c - 1 duplications) such that x * c >= k while minimizing (x - 1) + (c - 1).
  • Using the observation above, we can reframe the problem: For each possible final count c (>=1), compute the minimum increments needed as ceil(k / c) - 1 and then add the duplications (c - 1). The overall answer is the minimum value of (ceil(k / c) + c - 2) over all valid c.

Space and Time Complexity

Time Complexity: O(k) in worst-case (since k ≤ 10^5, iterating over possible counts is acceptable). Space Complexity: O(1) extra space.

Solution

The approach is to iterate over all possible counts (c) for the final elements in the array. For each value of c, we compute the minimum value of x (by taking the ceiling of k/c) such that x * c >= k. Then, the operations are the increments (x - 1) plus duplications (c - 1). We choose the minimum total operations among all possible c.

Edge Case: If k is 1, the initial array [1] already satisfies the condition, so no operations are needed.

Code Solutions

# Python implementation for the problem

import math

def minOperations(k: int) -> int:
    # if initial sum (which is 1) >= k, then no operations are needed
    if k <= 1:
        return 0
    
    min_ops = float('inf')
    # Iterate over possible final count (c) of elements from 1 to k (upper bound)
    for c in range(1, k + 1):
        # Calculate minimum x such that x * c >= k (using ceiling division)
        x = (k + c - 1) // c  # same as math.ceil(k / c)
        # Total operations: (x - 1) increments + (c - 1) duplicates
        ops = (x - 1) + (c - 1)
        # update minimum operations across all choices for c
        min_ops = min(min_ops, ops)
    return min_ops

# Example usage:
print(minOperations(11))  # Expected 5 for the example
← Back to All Questions