You are not logged in. Please login at www.codechef.com to post your questions!

×

HBDANA - Editorial

0
1

PROBLEM LINK:

Practice
Contest

Setter: Aakash Jaiswal

Tester: Deepansh Parmani

Editorialist: Akash Bhalotia

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Sorting

PROBLEM:

Given an array of size N, find the sum of the K largest elements of the array.

QUICK EXPLANATION:

Sort the array in non-decreasing or ascending order. Find the sum of the last K elements.

EXPLANATION:

One of the simplest ways to solve this problem is to use Sorting.

As 1 $\leq$ N $\leq$ 2* $10^5$, O($N^2$) sorting algorithms like Bubble Sort, Selection Sort, Insertion Sort, etc. would result in Time Limit Exceeded (TLE). Thus we have to use faster sorting algorithms like Merge Sort, Quick Sort, Heap Sort, etc. which generally result in a time complexity of O(NlogN).

In CP (Competitive Programming), one doesn't generally implement the full sorting algorithm, but uses in-built library sorting function of the language;

For Example:

  1. Arrays.sort() of JAVA
  2. qsort() of C
  3. sort() of C++

1) Sort the array in ascending order. Now the K-largest elements are all populated towards the end of the array, from index (N-K+1) to index N, 1-based indexing.

2) Using a loop, you can find the sum of the last K elements of this sorted array. A 32-bit integer datatype should be sufficient to store the sum, as $1\leq a[i]\leq 10^4$ and $1\leq K \leq 20$.

Another way to solve this problem, using sorting, is to sort the array in descending order and find the sum of the first K elements in it.

COMPLEXITY:

Time complexity: O(NlogN) per test case

Space Complexity: O(N)

SOLUTIONS:

Editorialist's solution

Similar Problem:

Find the sum of the K-smallest elements of the array. Same constraints.

===============================================

ALTERNATIVE SOLUTION:

1) O(N*K) using Looping:

View Content

2) O(N*logK) using a Min-Heap:

Heap

View Content

USEFUL READ-UPS AND TUTORIALS:

Don't know a topic? No worries :) You'll find the links below useful.

View Content

===============================================

BONUS:

Can we solve this problem in O(N) time?

View Content

==================================================================================================

Feel free to share your approach if it differs. If you have any doubts or you feel stuck at any point, feel free to ask them below. You can also reach me at $akashbhalotia\.unofficial@gmail\.com$ . I tried my best to make the editorial beginner-friendly. Suggestions are always welcomed :)

This question is marked "community wiki".

asked 26 Aug '18, 14:55

akashbhalotia's gravatar image

4★akashbhalotia
68112
accept rate: 14%

edited 26 Jan, 15:01

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,684
×1,652
×791
×28
×6

question asked: 26 Aug '18, 14:55

question was seen: 199 times

last updated: 26 Jan, 15:01