# Posts published in “Greedy”

You are given two integers, n and k.

An array of distinct positive integers is called a k-avoiding array if there does not exist any pair of distinct elements that sum to k.

Return the minimum possible sum of a k-avoiding array of length n.

Example 1:

Input: n = 5, k = 4
Output: 18
Explanation: Consider the k-avoiding array [1,2,4,5,6], which has a sum of 18.
It can be proven that there is no k-avoiding array with a sum less than 18.


Example 2:

Input: n = 2, k = 6
Output: 3
Explanation: We can construct the array [1,2], which has a sum of 3.
It can be proven that there is no k-avoiding array with a sum less than 3.


Constraints:

• 1 <= n, k <= 50

## Solution 1: Greedy + HashTable

Always choose the smallest possible number starting from 1.

Add all chosen numbers into a hashtable. For a new candidate i, check whether k – i is already in the hashtable.

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

## C++

You are given two integers, num and t.

An integer x is called achievable if it can become equal to num after applying the following operation no more than t times:

• Increase or decrease x by 1, and simultaneously increase or decrease num by 1.

Return the maximum possible achievable number. It can be proven that there exists at least one achievable number.

Example 1:

Input: num = 4, t = 1
Output: 6
Explanation: The maximum achievable number is x = 6; it can become equal to num after performing this operation:
1- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
It can be proven that there is no achievable number larger than 6.


Example 2:

Input: num = 3, t = 2
Output: 7
Explanation: The maximum achievable number is x = 7; after performing these operations, x will equal num:
1- Decrease x by 1, and increase num by 1. Now, x = 6 and num = 4.
2- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
It can be proven that there is no achievable number larger than 7.


Constraints:

• 1 <= num, t <= 50

## Solution: Greedy

Always decrease x and always increase num, the max achievable number x = num + t * 2

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

## C++

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:

1. Select an element m from nums.
2. Remove the selected element m from the array.
3. Add a new element with a value of m + 1 to the array.
4. Increase your score by m.

Return the maximum score you can achieve after performing the operation exactly k times.

Example 1:

Input: nums = [1,2,3,4,5], k = 3
Output: 18
Explanation: We need to choose exactly 3 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6]
For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7]
For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8]
So, we will return 18.
It can be proven, that 18 is the maximum answer that we can achieve.


Example 2:

Input: nums = [5,5,5], k = 2
Output: 11
Explanation: We need to choose exactly 2 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6]
For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7]
So, we will return 11.
It can be proven, that 11 is the maximum answer that we can achieve.


Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

## Solution: Greedy

Always to chose the largest element from the array.

We can find the largest element of the array m, then the total score will be
m + (m + 1) + (m + 2) + … + (m + k – 1),
We can use summation formula of arithmetic sequence to compute that in O(1)
ans = (m + (m + k – 1)) * k / 2

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

## C++

You are given a 0-indexed integer array nums. You can rearrange the elements of nums to any order (including the given order).

Let prefix be the array containing the prefix sums of nums after rearranging it. In other words, prefix[i] is the sum of the elements from 0 to i in nums after rearranging it. The score of nums is the number of positive integers in the array prefix.

Return the maximum score you can achieve.

Example 1:

Input: nums = [2,-1,0,1,-3,3,-3]
Output: 6
Explanation: We can rearrange the array into nums = [2,3,1,-1,-3,0,-3].
prefix = [2,5,6,5,2,2,-1], so the score is 6.
It can be shown that 6 is the maximum score we can obtain.


Example 2:

Input: nums = [-2,-3,0]
Output: 0
Explanation: Any rearrangement of the array will result in a score of 0.


Constraints:

• 1 <= nums.length <= 105
• -106 <= nums[i] <= 106

## Solution: Greedy

Sort the numbers in descending order.

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

## C++

You are given an integer array banned and two integers n and maxSum. You are choosing some number of integers following the below rules:

• The chosen integers have to be in the range [1, n].
• Each integer can be chosen at most once.
• The chosen integers should not be in the array banned.
• The sum of the chosen integers should not exceed maxSum.

Return the maximum number of integers you can choose following the mentioned rules.

Example 1:

Input: banned = [1,6,5], n = 5, maxSum = 6
Output: 2
Explanation: You can choose the integers 2 and 4.
2 and 4 are from the range [1, 5], both did not appear in banned, and their sum is 6, which did not exceed maxSum.


Example 2:

Input: banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
Output: 0
Explanation: You cannot choose any integer while following the mentioned conditions.


Example 3:

Input: banned = [11], n = 7, maxSum = 50
Output: 7
Explanation: You can choose the integers 1, 2, 3, 4, 5, 6, and 7.
They are from the range [1, 7], all did not appear in banned, and their sum is 28, which did not exceed maxSum.


Constraints:

• 1 <= banned.length <= 104
• 1 <= banned[i], n <= 104
• 1 <= maxSum <= 109

## Solution 1: Greedy + HashSet

We would like to use the smallest numbers possible. Store all the banned numbers into a hashset, and enumerate numbers from 1 to n and check whether we can use that number.

Time complexity: O(m + n)
Space complexity: O(m)

## Solution 2: Two Pointers

Sort the banned numbers. Use one pointer j and compare with the current number i.

Time complexity: O(mlogm + n)
Space complexity: O(1)