2656. Maximum Sum With Exactly K Elements

Problem Description

You are provided with an array nums, which contains integer elements and is indexed starting from 0. Along with this, you are given an integer k. The goal is to maximize your score through a specific operation that you can perform exactly k times.

The operation consists of the following steps:

Pick an element m from the array nums.
Remove this element from the array.
Insert a new element into the array that has a value of m + 1.
Increase your score by m.

After performing this operation exactly k times, you need to determine the maximum score you can achieve.

Intuition

To maximize the score from each operation, it's logical to always select the largest element available in the array. If you always choose the largest element, which we will denote as x, you ensure that your score increments by the maximum possible value each time.

Here's the thinking process step by step:

In the first operation, choose the maximum element in the array, x. Your score increases by x and now the array has a new element x + 1.
For the second operation, since you now have x + 1 in the array (which is greater than the original x), you select and remove x + 1, and then add x + 2. Your score increases by x + 1 this time.
You continue this process, each time selecting the current maximum, which continues to increase by 1 with each operation.

After k operations, your total score will be an accumulated sum of all selected elements: x from the first operation, x + 1 from the second, and so on, up to x + k - 1 for the kth operation.

So, you can calculate the total score by taking the sum of the arithmetic sequence that starts with x, has k terms, and a common difference of 1.

Thus, the formula to calculate the final score is:

Score = k * x + (1 + 2 + ... + (k - 1))

We can simplify the summation using the formula for the sum of the first n natural numbers:

Sum = n * (n + 1) / 2

Therefore, you can express the score as:

Score = k * x + (k - 1) * k / 2

Applying this formula grants us the maximum score after k operations without the need to simulate the operations step by step.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Solution Approach

The solution outlined above hinges on understanding and applying a mathematical concept rather than running complex algorithms or relying on particular data structures. Here's how we translate the mathematical solution into a concrete implementation:

First, we need to determine the maximum element from the array nums, which is denoted as x. In Python, this can be easily done by using the built-in max() function.
```
1x = max(nums)
```
Now that we have the maximum number (x), we must calculate the score based on the formula derived earlier:

Score = k * x + (k - 1) * k / 2

In the formula, k * x accounts for selecting the maximum element x k times, while the second part of the formula (k - 1) * k / 2 is the sum of the arithmetic series contributing to the incrementality of the score with each operation.
The implementation of this calculation is straightforward and directly derived from the formula. It can be written in a single line of code in Python:
```
1return k * x + k * (k - 1) // 2
```
Here, the // operator is used to perform integer division to avoid any floating-point result, which is suitable since we are dealing with integers only.

By abstracting the problem into a formula, the time complexity of the solution is O(n), where n is the length of the array, coming from the time complexity of finding the maximum element. The space complexity is O(1), as we only store the maximum element and use no additional data structures to hold intermediate values.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose our input array nums is [3, 5, 2] and we are allowed to perform the operation k = 2 times.

We first find the maximum element in the array, which is x = 5.
Then, we calculate the maximum score by using the earlier derived formula:

Score = k * x + (k - 1) * k / 2

Plugging in the values:

Score = 2 * 5 + (2 - 1) * 2 / 2 Score = 10 + 1 Score = 11

So, without physically removing elements and adding them back to the array, we can directly compute that the maximum score after performing the operation twice is 11.

To break it down further, after the first operation, we would have selected element 5, removed it, added 6 to the array, and increased our score by 5. After the second operation, we would select the new maximum element, which is 6, remove it, add 7 to the array, and increase our score by another 6. Therefore, the total score would be 5 (initial score) + 6 (second operation) = 11.

This hypothetical set of operations confirms the correctness of our direct calculation using the formula. The formula saves time by avoiding multiple iterations for selecting and replacing elements with their increments.

Implementing this step-by-step:

From array nums = [3, 5, 2], find the maximum element x, which is 5.
Calculate the maximum score using the given values k = 2 and x = 5.
Substitute into the formula to get the result: Score = 2 * 5 + 1 * (2 - 1) = 11.

A Python implementation of this example would be:

1nums = [3, 5, 2]
2k = 2
3
4x = max(nums)
5score = k * x + k * (k - 1) // 2
6
7print(score)  # Output should be 11

This program would output 11, which represents the maximum score achieved after performing the operation k times.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximizeSum(self, nums: List[int], k: int) -> int:
5        # Find the maximum number in the given list of numbers
6        max_num = max(nums)
7
8        # The strategy to maximize the sum is to repeatedly increment the maximum number.
9        # We will do this k times, each time adding the maximum number to the sum.
10        # And for each iteration, we also add the i-th increment (0 to k-1).
11        # This is equivalent to max_num * k (adding max_num k times), plus the sum
12        # of the first k natural numbers, which is k * (k - 1) // 2 using the formula for the sum
13        # of the first 'n' natural numbers.
14        maximized_sum = k * max_num + k * (k - 1) // 2
15
16        # Return the calculated maximized sum
17        return maximized_sum
18

1class Solution {
2    public int maximizeSum(int[] nums, int k) {
3        // Initialize a variable to store the maximum value found in the array
4        int maxVal = 0;
5
6        // Iterate through all elements in the array to find the maximum value
7        for (int value : nums) {
8            maxVal = Math.max(maxVal, value);
9        }
10
11        // Calculate and return the sum of the largest k numbers in an arithmetic progression
12        // starting from maxVal and with a common difference of 1.
13        return k * maxVal + k * (k - 1) / 2;
14    }
15}
16

1#include <vector>
2#include <algorithm> // Include algorithm for std::max_element
3
4class Solution {
5public:
6    // Function to maximize sum by performing k increments on the maximum element
7    int maximizeSum(std::vector<int>& nums, int k) {
8        // Find the maximum element in the vector
9        int maxElement = *std::max_element(nums.begin(), nums.end());
10      
11        // Calculate the total increment on the max element after k operations
12        // This is done by multiplying the maximum element with k
13        // And then adding the sum of first k natural numbers (k*(k-1)/2)
14        int totalIncrement = k * maxElement + k * (k - 1) / 2;
15      
16        // Return the sum after all increments are done
17        return totalIncrement;
18    }
19};
20

1/**
2 * Maximizes the sum by adding the top k numbers where the
3 * first number is the maximum in the array and every subsequent
4 * number is one less than the previous.
5 * 
6 * @param {number[]} nums - The array of numbers to search through.
7 * @param {number} k - The number of top elements to consider for maximizing the sum.
8 * @returns {number} The maximized sum according to the described formula.
9 */
10function maximizeSum(nums: number[], k: number): number {
11    // Find the maximum value in the nums array.
12    const maxValue = Math.max(...nums);
13    // Calculate the sum of the top k numbers starting from the maxValue.
14    // The formula used is the sum of the first k elements of an arithmetic series
15    // starting with maxValue and decrementing by 1 each time.
16    const sum = k * maxValue + (k * (k - 1)) / 2;
17
18    // Return the calculated sum.
19    return sum;
20}
21

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

The given Python code consists of two main operations: finding the maximum value in the list nums, and performing arithmetic calculations to obtain the result.

Time Complexity

The time complexity of finding the maximum element in a list of n elements using max(nums) is O(n), as it requires checking each element exactly once. The arithmetic operations k * x + k * (k - 1) // 2 involve constant time calculations, hence their complexity is O(1).

Overall, the time complexity of the function is O(n) + O(1), which simplifies to O(n).

Space Complexity

In terms of space complexity, there are no additional data structures used that grow with the input size. Only a constant amount of additional space is used for variables like x. Therefore, the space complexity of the function is O(1).

In conclusion, the time complexity of the provided code is O(n) and the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2656. Maximum Sum With Exactly K Elements

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings