# Apply Operations to Make Sum of Array Greater Than or Equal to k
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/apply-operations-to-make-sum-of-array-greater-than-or-equal-to-k)
Canonical: https://scaleengineer.com/dsa/problems/apply-operations-to-make-sum-of-array-greater-than-or-equal-to-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Companies:** [ZScaler](https://scaleengineer.com/companies/zscaler), [Turing](https://scaleengineer.com/companies/turing)
---
## Problem
You are given a **positive** integer `k`. Initially, you have an array `nums = [1]`.

You can perform **any** of the following operations on the array **any** number of times (**possibly zero**):

* Choose any element in the array and **increase** its value by `1`.
* Duplicate any element in the array and add it to the end of the array.

Return _the **minimum** number of operations required to make the **sum** of elements of the final array greater than or equal to_ `k`.

**Example 1:**

**Input:** k = 11

**Output:** 5

**Explanation:**

We can do the following operations on the array `nums = [1]`:

* Increase the element by `1` three times. The resulting array is `nums = [4]`.
* Duplicate the element two times. The resulting array is `nums = [4,4,4]`.

The sum of the final array is `4 + 4 + 4 = 12` which is greater than or equal to `k = 11`.  
The total number of operations performed is `3 + 2 = 5`.

**Example 2:**

**Input:** k = 1

**Output:** 0

**Explanation:**

The sum of the original array is already greater than or equal to `1`, so no operations are needed.

**Constraints:**

* `1 <= k <= 105`

# Approaches
## Brute Force Iteration
This approach involves a straightforward linear scan through all potential values for the elements in the final array. For each potential value `v`, we calculate the required number of elements `c` and the corresponding total operations. By iterating through all sensible values of `v`, we can find the minimum number of operations required.
**Time:** O(k) - The main part of the algorithm is a single loop that runs from 1 to `k`. All operations inside the loop are constant time. · **Space:** O(1) - We only use a few variables to store the minimum operations and loop counters, regardless of the input size `k`.
**Pros:** The logic is simple and easy to understand.; It is guaranteed to find the correct answer for the given constraints.
**Cons:** This approach can be slow if `k` is very large, as the time complexity is directly proportional to `k`.
### Explanation
The fundamental insight is that the most efficient way to construct the final array is to have all its elements be identical. Let's say we decide to create an array of `c` elements, each with a value of `v`.

To achieve this from the initial array `[1]`, we need to perform two types of operations:
1.  **Increment Operations**: To change the initial element `1` to `v`, we need `v - 1` increments.
2.  **Duplicate Operations**: To get an array of `c` elements from a single element, we need `c - 1` duplications.

The total number of operations is `(v - 1) + (c - 1)`.

The sum of the array elements will be `v * c`. To satisfy the problem condition, we must have `v * c >= k`.

To minimize operations for a fixed `v`, we should choose the smallest possible integer `c` that satisfies the condition. This value is `c = ceil(k / v)`. In integer arithmetic, this is calculated as `c = (k + v - 1) / v`.

This approach iterates through all possible values of `v` from 1 up to `k`, calculates the corresponding `c` and the total operations, and finds the minimum among them.

```java
class Solution {
    public int minOperations(int k) {
        if (k == 1) {
            return 0;
        }
        // An initial upper bound is k-1 operations.
        // This can be achieved by setting v=k, c=1 (k-1 increments, 0 duplicates)
        // or v=1, c=k (0 increments, k-1 duplicates).
        int minOps = k - 1;

        // Iterate through all possible values 'v' from 1 to k.
        for (int v = 1; v <= k; v++) {
            // For a given v, the minimum count 'c' needed is ceil(k/v).
            int c = (k + v - 1) / v;
            
            // Total operations = (increment ops) + (duplicate ops)
            int currentOps = (v - 1) + (c - 1);
            
            minOps = Math.min(minOps, currentOps);
        }
        
        return minOps;
    }
}
```
### Algorithm
- Handle the edge case: if `k` is 1, the initial array `[1]` is sufficient, so return 0.
- The total number of operations is the sum of increment operations and duplicate operations. A known upper bound for the minimum operations is `k - 1` (achieved by either incrementing the initial `1` to `k`, or by duplicating the `1` `k-1` times).
- We can iterate through all possible values `v` that the elements in the final array could have. A reasonable range for `v` is from 1 to `k`.
- For each value `v`, we determine the minimum number of elements `c` needed to make the sum at least `k`. This is given by `c = ceil(k / v)`, which can be calculated using integer arithmetic as `c = (k + v - 1) / v`.
- The number of increment operations to get value `v` is `v - 1`.
- The number of duplicate operations to get `c` elements is `c - 1`.
- The total operations for a given `v` is `(v - 1) + (c - 1)`.
- We keep track of the minimum total operations found across all tested values of `v`.
- After checking all `v` from 1 to `k`, the minimum value found is the answer.

## Optimized Search with Square Root
This approach optimizes the brute-force method by reducing the search space. It's based on the mathematical property that for the optimal pair of value `v` and count `c`, at least one of them must be less than or equal to the square root of `k`. This drastically cuts down the number of iterations needed.
**Time:** O(sqrt(k)) - The algorithm performs two loops, each running up to `sqrt(k)` times. This is a major improvement over the linear scan. · **Space:** O(1) - Constant extra space is used.
**Pros:** Significantly faster than the O(k) brute-force approach.; Still relatively simple to implement.
**Cons:** Slightly more complex to reason about than the simple brute-force approach.
### Explanation
We are trying to minimize the function `ops(v, c) = v + c - 2` subject to `v * c >= k`.

The expression `v + c` is minimized when `v` and `c` are close to each other. For a fixed product `v*c = P`, the sum `v+c` is minimized when `v = c = sqrt(P)`. This suggests that our optimal integer solution `(v, c)` will be close to the point `(sqrt(k), sqrt(k))` on the `v-c` plane.

Let's prove that for an optimal solution `(v_opt, c_opt)`, we must have `min(v_opt, c_opt) <= sqrt(k)`. Assume for contradiction that `v_opt > sqrt(k)` and `c_opt > sqrt(k)`. Then their product `v_opt * c_opt > k`. This means the solution is not 'tight'. We could potentially decrease `v_opt` to `v_opt - 1` and still satisfy the sum constraint, while reducing the total operations. A more formal proof shows that one of the two must be less than or equal to `sqrt(k)`.

This observation allows us to limit our search. We only need to check pairs `(v, c)` where at least one component is small.

1.  We iterate through all small values of `v` (i.e., `v` from 1 to `sqrt(k)`). For each `v`, we find the best `c` and calculate the operations.
2.  We iterate through all small values of `c` (i.e., `c` from 1 to `sqrt(k)`). For each `c`, we find the best `v` and calculate the operations. This second loop covers the cases where `v` is large (since if `v > sqrt(k)`, then `c` must be small).

```java
class Solution {
    public int minOperations(int k) {
        if (k == 1) {
            return 0;
        }
        int minOps = k - 1;
        int limit = (int) Math.sqrt(k);

        // Case 1: Iterate through v from 1 to sqrt(k).
        // This covers all pairs where v is small.
        for (int v = 1; v <= limit; v++) {
            int c = (k + v - 1) / v;
            minOps = Math.min(minOps, (v - 1) + (c - 1));
        }

        // Case 2: Iterate through c from 1 to sqrt(k).
        // This covers all pairs where c is small (and v is large).
        // Note: There is some overlap with Case 1, but it's harmless.
        for (int c = 1; c <= limit; c++) {
            int v = (k + c - 1) / c;
            minOps = Math.min(minOps, (v - 1) + (c - 1));
        }

        return minOps;
    }
}
```
### Algorithm
- The problem is to minimize `(v - 1) + (c - 1)` subject to `v * c >= k`.
- The optimal integer solution `(v, c)` for this problem will have the property that `min(v, c) <= sqrt(k)`.
- This insight allows us to avoid checking all `v` up to `k`. We can split the search into two parts:
  1. Cases where `v <= sqrt(k)`.
  2. Cases where `c <= sqrt(k)` (which covers the remaining cases where `v > sqrt(k)`).
- First, iterate `v` from 1 up to `floor(sqrt(k))`. For each `v`, calculate `c = ceil(k/v)` and the total operations, updating the minimum.
- Second, iterate `c` from 1 up to `floor(sqrt(k))`. For each `c`, calculate the required `v = ceil(k/c)` and the total operations, updating the minimum.
- The overall minimum found after these two loops is the answer.

## Ternary Search
This is the most efficient approach, which treats the problem as finding the minimum of a mathematical function. The number of operations, when viewed as a function of the element value `v`, is unimodal (it first decreases and then increases). This property allows for a ternary search, which can find the minimum in logarithmic time, making it extremely fast.
**Time:** O(log k) - Ternary search reduces the search space of size `k` by a constant factor at each step. · **Space:** O(1) - The search is done in-place with a few variables.
**Pros:** Extremely efficient, with logarithmic time complexity.; It is the most optimal solution for this problem.
**Cons:** The implementation is more complex than iterative solutions.; It relies on correctly identifying the unimodal property of the cost function.
### Explanation
The cost function we want to minimize is `f(v) = (v - 1) + (ceil(k / v) - 1)`. Let's analyze its components:
- `v - 1`: This term increases linearly with `v`.
- `ceil(k / v) - 1`: This term decreases as `v` increases.

The sum of a strictly increasing function and a strictly decreasing function results in a convex or unimodal function. The `ceil` operation introduces some steps, but the overall shape remains unimodal. This means there's a single valley, and we can use an efficient search algorithm to find its bottom.

Ternary search is designed for this exact scenario. It's similar to binary search but divides the search space into three parts instead of two. By evaluating the function at two points (`m1` and `m2`), it can eliminate one-third of the search space in each step, leading to a logarithmic time complexity.

```java
class Solution {
    public int minOperations(int k) {
        if (k == 1) {
            return 0;
        }

        long low = 1, high = k;
        long minOps = k - 1; // Initial upper bound

        // Ternary search to find the 'v' that minimizes the operations.
        // The function f(v) = (v-1) + (ceil(k/v)-1) is unimodal.
        while (high - low >= 3) {
            long m1 = low + (high - low) / 3;
            long m2 = high - (high - low) / 3;
            if (calculateOps(m1, k) < calculateOps(m2, k)) {
                high = m2;
            } else {
                low = m1;
            }
        }

        // After the loop, the minimum is in the small range [low, high].
        // We check this range exhaustively.
        for (long v = low; v <= high; v++) {
            minOps = Math.min(minOps, calculateOps(v, k));
        }

        return (int) minOps;
    }

    // Helper function to calculate operations for a given value 'v'.
    private long calculateOps(long v, int k) {
        if (v == 0) return Long.MAX_VALUE;
        long c = (k + v - 1) / v; // c = ceil(k/v)
        return (v - 1) + (c - 1);
    }
}
```
### Algorithm
- The function to minimize is `f(v) = (v - 1) + (ceil(k / v) - 1)`.
- This function is unimodal, meaning it has a single minimum value over the search range `[1, k]`.
- We can use ternary search to find the value of `v` that minimizes this function.
- Initialize a search range `low = 1` and `high = k`.
- Repeatedly shrink the search range: 
  - Calculate two midpoints `m1 = low + (high - low) / 3` and `m2 = high - (high - low) / 3`.
  - Compare `f(m1)` and `f(m2)`.
  - If `f(m1) < f(m2)`, the minimum must lie in the interval `[low, m2]`, so we set `high = m2`.
  - Otherwise, the minimum must lie in `[m1, high]`, so we set `low = m1`.
- Continue this until the range `[low, high]` is very small (e.g., `high - low < 3`).
- Finally, perform a linear scan over the small remaining interval `[low, high]` to find the exact minimum.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int k) {
    int ans = k;
    for (int a = 0; a < k; ++a) {
      int x = a + 1;
      int b = (k + x - 1) / x - 1;
      ans = Math.min(ans, a + b);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(int k) {
    int ans = k;
    for (int a = 0; a < k; ++a) {
      int x = a + 1;
      int b = (k + x - 1) / x - 1;
      ans = min(ans, a + b);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, k: int) -> int: ans = k for a in range(k): x = a + 1 b = (k + x - 1) // x - 1 ans = min(ans, a + b) return ans

```