Posts tagged as “greedy”

花花酱 LeetCode 2233. Maximum Product After K Increments

By zxi on April 9, 2022

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

Constraints:

1 <= nums.length, k <= 10⁵
0 <= nums[i] <= 10⁶

Solution: priority queue

Always increment the smallest number. Proof?

Time complexity: O(klogn + nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maximumProduct(vector<int>& nums, int k) {

constexpr int kMod = 1e9 + 7;

priority_queue<int, vector<int>, greater<int>> q(begin(nums), end(nums));

while (k--) {

const int n = q.top();

q.pop();

q.push(n + 1);

}

long long ans = 1;

while (!q.empty()) {

ans *= q.top(); q.pop();

ans %= kMod;

}

return ans;

}

};

花花酱 LeetCode 2224. Minimum Number of Operations to Convert Time

By zxi on April 2, 2022

You are given two strings current and correct representing two 24-hour times.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.

Return the minimum number of operations needed to convert current to correct.

Example 1:

Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.

Example 2:

Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.

Constraints:

current and correct are in the format "HH:MM"
current <= correct

Solution: Greedy

Start with 60, then 15, 5 and finally increase 1 minute a time.

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int convertTime(string current, string correct) {

auto getMinute = [](string_view t) {

return (t[0] - '0') * 10 * 60

+ (t[1] - '0') * 60

+ (t[3] - '0') * 10

+ (t[4] - '0');

};

int t1 = getMinute(current);

int t2 = getMinute(correct);

int ans = 0;

for (int d : {60, 15, 5, 1})

while (t2 - t1 >= d) {

++ans;

t1 += d;

}

return ans;

}

};

花花酱 LeetCode 2208. Minimum Operations to Halve Array Sum

By zxi on March 21, 2022

You are given an array nums of positive integers. In one operation, you can choose any number from nums and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of nums by at least half.

Example 1:

Input: nums = [5,19,8,1]
Output: 3
Explanation: The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33.
The following is one of the ways to reduce the sum by at least half:
Pick the number 19 and reduce it to 9.5.
Pick the number 9.5 and reduce it to 4.75.
Pick the number 8 and reduce it to 4.
The final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75. 
The sum of nums has been reduced by 33 - 14.75 = 18.25, which is at least half of the initial sum, 18.25 >= 33/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Example 2:

Input: nums = [3,8,20]
Output: 3
Explanation: The initial sum of nums is equal to 3 + 8 + 20 = 31.
The following is one of the ways to reduce the sum by at least half:
Pick the number 20 and reduce it to 10.
Pick the number 10 and reduce it to 5.
Pick the number 3 and reduce it to 1.5.
The final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5. 
The sum of nums has been reduced by 31 - 14.5 = 16.5, which is at least half of the initial sum, 16.5 >= 31/2 = 16.5.
Overall, 3 operations were used so we return 3.
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁷

Solution: Greedy + PriorityQueue/Max Heap

Always half the largest number, put all the numbers onto a max heap (priority queue), extract the largest one, and put reduced number back.

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int halveArray(vector<int>& nums) {

double sum = accumulate(begin(nums), end(nums), 0.0);

priority_queue<double> q;

for (int num : nums) q.push(num);

int ans = 0;

for (double cur = sum; cur > sum / 2; ++ans) {

double num = q.top(); q.pop();

cur -= num / 2;

q.push(num / 2);

}

return ans;

}

};

花花酱 LeetCode 2195. Append K Integers With Minimal Sum

By zxi on March 8, 2022

You are given an integer array nums and an integer k. Append k unique positive integers that do not appear in nums to nums such that the resulting total sum is minimum.

Return the sum of the k integers appended to nums.

Example 1:

Input: nums = [1,4,25,10,25], k = 2
Output: 5
Explanation: The two unique positive integers that do not appear in nums which we append are 2 and 3.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.

Example 2:

Input: nums = [5,6], k = 6
Output: 25
Explanation: The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. 
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁸

Solution: Greedy + Math, fill the gap

Sort all the numbers and remove duplicated ones, and fill the gap between two neighboring numbers.
e.g. [15, 3, 8, 8] => sorted = [3, 8, 15]
fill 0->3, 1,2, sum = ((0 + 1) + (3-1)) * (3-0-1) / 2 = 3
fill 3->8, 4, 5, 6, 7, sum = ((3 + 1) + (8-1)) * (8-3-1) / 2 = 22
fill 8->15, 9, 10, …, 14, …
fill 15->inf, 16, 17, …

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long minimalKSum(vector<int>& nums, int k) {

sort(begin(nums), end(nums));

long long ans = 0;

long long p = 0;

for (int c : nums) {

if (c == p) continue;

long long n = min((long long)k, c - p - 1);

ans += (p + 1 + p + n) * n / 2;

k -= n;

p = c;

}

ans += (p + 1 + p + k) * k / 2;

return ans;

}

};

花花酱 LeetCode 2178. Maximum Split of Positive Even Integers

By zxi on March 4, 2022

You are given an integer finalSum. Split it into a sum of a maximum number of unique positive even integers.

For example, given finalSum = 12, the following splits are valid (unique positive even integers summing up to finalSum): (12), (2 + 10), (2 + 4 + 6), and (4 + 8). Among them, (2 + 4 + 6) contains the maximum number of integers. Note that finalSum cannot be split into (2 + 2 + 4 + 4) as all the numbers should be unique.

Return a list of integers that represent a valid split containing a maximum number of integers. If no valid split exists for finalSum, return an empty list. You may return the integers in any order.

Example 1:

Input: finalSum = 12
Output: [2,4,6]
Explanation: The following are valid splits: (12), (2 + 10), (2 + 4 + 6), and (4 + 8).
(2 + 4 + 6) has the maximum number of integers, which is 3. Thus, we return [2,4,6].
Note that [2,6,4], [6,2,4], etc. are also accepted.

Example 2:

Input: finalSum = 7
Output: []
Explanation: There are no valid splits for the given finalSum.
Thus, we return an empty array.

Example 3:

Input: finalSum = 28
Output: [6,8,2,12]
Explanation: The following are valid splits: (2 + 26), (6 + 8 + 2 + 12), and (4 + 24). 
(6 + 8 + 2 + 12) has the maximum number of integers, which is 4. Thus, we return [6,8,2,12].
Note that [10,2,4,12], [6,2,4,16], etc. are also accepted.

Constraints:

1 <= finalSum <= 10¹⁰

Solution: Greedy

The get the maximum number of elements, we must use the smallest numbers.

[2, 4, 6, …, 2k, x], where x > 2k
let s = 2 + 4 + … + 2k, x = num – s
since num is odd and s is also odd, so thus x = num – s.

Time complexity: O(sqrt(num)) for constructing outputs.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<long long> maximumEvenSplit(long long finalSum) {

if (finalSum & 1) return {};

vector<long long> ans;

long long s = 0;

for (long long i = 2; s + i <= finalSum; s += i, i += 2)

ans.push_back(i);

ans.back() += (finalSum - s);

return ans;

}

};