Given an array A[] of size N and a positive integer K ( which will always be a factor of N), the task is to find the maximum possible sum of the second smallest elements of each partition of the array by partitioning the array into (N / K) partitions of equal size.
Examples:
Input: A[] = {2, 3, 1, 4, 7, 5, 6, 1}, K = 4
Output: 7
Explanation: Split the array as {1, 2, 3, 4} and {1, 5, 6, 7}. Therefore, sum = 2 + 5 = 7, which is the maximum possible sum.Input: A[] = {12, 43, 15, 32, 45, 23}, K = 3
Output : 66
Explanation: Split the array as {12, 23, 32} and {15, 43, 45}. Therefore, sum = 23 + 43 = 66, which is the maximum possible sum.
Approach: The idea is to sort the given array in ascending order and in order to maximize the required sum, divide the first N / K elements of A[] to each of the arrays as their first term, then choose every (K – 1)th element of A[] starting from N/K.
Follow the steps below to solve the problem:
- Sort the array A[] in increasing order.
- Initialize sum with 0 to store the required sum.
- Now, initialize a variable i with N / K.
- While i is less than N, perform the following steps:
- Increment sum by A[i].
- Increment i by K – 1.
- After traversing, print sum as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// second smallest of each partition// of size Kvoid findSum(int A[], int N, int K){ // Sort the array A[] // in ascending order sort(A, A + N); // Store the maximum sum of second // smallest of each partition // of size K int sum = 0; // Select every (K-1)th element as // second smallest element for (int i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum cout << sum;}// Driver Codeint main(){ // Given size of partitions int K = 4; // Given array A[] int A[] = { 2, 3, 1, 4, 7, 5, 6, 1 }; // Size of the given array int N = sizeof(A) / sizeof(A[0]); // Function Call findSum(A, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum sum of// second smallest of each partition// of size Kstatic void findSum(int A[], int N, int K){ // Sort the array A[] // in ascending order Arrays.sort(A); // Store the maximum sum of second // smallest of each partition // of size K int sum = 0; // Select every (K-1)th element as // second smallest element for(int i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum System.out.print(sum);}// Driver Codepublic static void main(String[] args){ // Given size of partitions int K = 4; // Given array A[] int A[] = { 2, 3, 1, 4, 7, 5, 6, 1 }; // Size of the given array int N = A.length; // Function Call findSum(A, N, K);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to find the maximum sum of# second smallest of each partition# of size Kdef findSum(A, N, K): # Sort the array A # in ascending order A.sort(); # Store the maximum sum of second # smallest of each partition # of size K sum = 0; # Select every (K-1)th element as # second smallest element for i in range(N // K, N, K - 1): # Update sum sum += A[i]; # Print the maximum sum print(sum);# Driver Codeif __name__ == '__main__': # Given size of partitions K = 4; # Given array A A = [2, 3, 1, 4, 7, 5, 6, 1]; # Size of the given array N = len(A); # Function Call findSum(A, N, K); # This code contributed by shikhasingrajput |
C#
// C# program for the above approachusing System;class GFG{// Function to find the maximum sum of// second smallest of each partition// of size Kstatic void findSum(int []A, int N, int K){ // Sort the array []A // in ascending order Array.Sort(A); // Store the maximum sum of second // smallest of each partition // of size K int sum = 0; // Select every (K-1)th element as // second smallest element for(int i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum Console.Write(sum);}// Driver Codepublic static void Main(String[] args){ // Given size of partitions int K = 4; // Given array []A int []A = { 2, 3, 1, 4, 7, 5, 6, 1 }; // Size of the given array int N = A.Length; // Function Call findSum(A, N, K);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program of the above approach// Function to find the maximum sum of// second smallest of each partition// of size Kfunction findSum(A, N, K){ // Sort the array A[] // in ascending order A.sort(); // Store the maximum sum of second // smallest of each partition // of size K let sum = 0; // Select every (K-1)th element as // second smallest element for(let i = N / K; i < N; i += K - 1) { // Update sum sum += A[i]; } // Print the maximum sum document.write(sum);}// Driver Code// Given size of partitionslet K = 4;// Given array A[]let A = [ 2, 3, 1, 4, 7, 5, 6, 1 ];// Size of the given arraylet N = A.length;// Function CallfindSum(A, N, K);// This code is contributed by chinmoy1997pal</script> |
7
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
