3091. Apply Operations to Make Sum of Array Greater Than or Equal to k LeetCode Solution
In this guide, you will get 3091. Apply Operations to Make Sum of Array Greater Than or Equal to k LeetCode Solution with the best time and space complexity. The solution to Apply Operations to Make Sum of Array Greater Than or Equal to k problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Apply Operations to Make Sum of Array Greater Than or Equal to k
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
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(1)
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k LeetCode Solution in C++
class Solution {
public:
int minOperations(int k) {
// The required operations are
// 1. Increase `1` to `x`
// 2. Duplicate `x`, `y` times, to `sum` s.t. x * (1 + y) >= k.
// The number of operations used would be (x - 1) + y. Equivalently, the
// problem can be rephrased as finding min(x - 1 + y) s.t. x * (1 + y) >= k.
// Optimally, `x` should equal to `1 + y`, implying that x^2 >= k, and
// hence, x >= sqrt(k) and y = ceil(k / x) - 1.
const int x = ceil(sqrt(k));
const int y = (k - 1) / x + 1 - 1; // ceil(k / x) - 1
return x - 1 + y;
}
}; /* code provided by PROGIEZ */
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k LeetCode Solution in Java
class Solution {
public int minOperations(int k) {
// The required operations are
// 1. Increase `1` to `x`
// 2. Duplicate `x`, `y` times, to `sum` s.t. x * (1 + y) >= k.
// The number of operations used would be (x - 1) + y. Equivalently, the
// problem can be rephrased as finding min(x - 1 + y) s.t. x * (1 + y) >= k.
// Optimally, `x` should equal to `1 + y`, implying that x^2 >= k, and
// hence, x >= sqrt(k) and y = ceil(k / x) - 1.
final int x = (int) Math.ceil(Math.sqrt(k));
final int y = (k - 1) / x + 1 - 1; // ceil(k / x) - 1
return x - 1 + y;
}
} // code provided by PROGIEZ
3091. Apply Operations to Make Sum of Array Greater Than or Equal to k LeetCode Solution in Python
class Solution:
def minOperations(self, k: int) -> int:
# The required operations are
# 1. Increase `1` to `x`
# 2. Duplicate `x`, `y` times, to `sum` s.t. x * (1 + y) >= k.
# The number of operations used would be (x - 1) + y. Equivalently, the
# problem can be rephrased as finding min(x - 1 + y) s.t. x * (1 + y) >= k.
# Optimally, `x` should equal to `1 + y`, implying that x^2 >= k, and
# hence, x >= sqrt(k) and y = ceil(k / x) - 1.
x = math.ceil(math.sqrt(k))
y = (k - 1) // x + 1 - 1 # ceil(k / x) - 1
return x - 1 + y # code by PROGIEZ
