Given a sorted array arr[] consisting of N integers and a positive integer K(such that N%K is 0), the task is to find the minimum sum of the medians of all possible subsequences of size K such that each element belongs to only one subsequence.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 2
Output: 6
Explanation:
Consider the subsequences of size K as {1, 4}, {2, 5}, and {3, 6}.
The sum of medians of all the subsequences is (1 + 2 + 3) = 6 which is the minimum possible sum.Input: K = 3, arr[] = {3, 11, 12, 22, 33, 35, 38, 67, 69, 71, 94, 99}, K = 3
Output: 135
Naive Approach: The given problem can be solved by generating all possible K-sized sorted subsequences and print the median of all those subsequences as the result.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by using the Greedy Approach for the construction of all the subsequences. The idea is to select K/2 elements from starting of the array and K/2 elements from the ending of the array such that the median always occurs in the first part. Follow the steps below to solve the problem:
- Initialize a variable, say res that stores the resultant sum of medians.
- Initialize a variable, say T as N/K to store the number of subsequences required and a variable D as (K + 1)/2 to store the distance between the medians.
- Initialize a variable, say i as (D – 1) to store the index of the first median to be added to the result.
- Iterate until the value of i < N and T > 0, and perform the following steps:
- Add the value of arr[i] to the variable res.
- Increment the value of i by D to get the index of the next median.
- Decrement the value of T by 1.
- After completing the above steps, print the value of res as the result.
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 minimum sum of// all the medians of the K sized sorted// arrays formed from the given arrayvoid sumOfMedians(int arr[], int N, int K){ // Stores the distance between // the medians int selectMedian = (K + 1) / 2; // Stores the number of subsequences // required int totalArrays = N / K; // Stores the resultant sum int minSum = 0; // Iterate from start and add // all the medians int i = selectMedian - 1; while (i < N and totalArrays != 0) { // Add the value of arr[i] // to the variable minsum minSum = minSum + arr[i]; // Increment i by select the // median to get the next // median index i = i + selectMedian; // Decrement the value of // totalArrays by 1 totalArrays--; } // Print the resultant minimum sum cout << minSum;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof(arr) / sizeof(int); int K = 2; sumOfMedians(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class GFG { // Function to find the minimum sum of // all the medians of the K sized sorted // arrays formed from the given array static void sumOfMedians(int arr[], int N, int K) { // Stores the distance between // the medians int selectMedian = (K + 1) / 2; // Stores the number of subsequences // required int totalArrays = N / K; // Stores the resultant sum int minSum = 0; // Iterate from start and add // all the medians int i = selectMedian - 1; while (i < N && totalArrays != 0) { // Add the value of arr[i] // to the variable minsum minSum = minSum + arr[i]; // Increment i by select the // median to get the next // median index i = i + selectMedian; // Decrement the value of // totalArrays by 1 totalArrays--; } // Print the resultant minimum sum System.out.println(minSum); } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = arr.length; int K = 2; sumOfMedians(arr, N, K); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to find the minimum sum of# all the medians of the K sized sorted# arrays formed from the given arraydef sumOfMedians(arr, N, K): # Stores the distance between # the medians selectMedian = (K + 1) // 2 # Stores the number of subsequences # required totalArrays = N // K # Stores the resultant sum minSum = 0 # Iterate from start and add # all the medians i = selectMedian - 1 while (i < N and totalArrays != 0): # Add the value of arr[i] # to the variable minsum minSum = minSum + arr[i] # Increment i by select the # median to get the next # median index i = i + selectMedian # Decrement the value of # totalArrays by 1 totalArrays -= 1 # Print the resultant minimum sum print(minSum) # Driver Codeif __name__ == '__main__': arr = [ 1, 2, 3, 4, 5, 6 ] N = len(arr) K = 2 sumOfMedians(arr, N, K)# This code is contributed by nirajgsuain5 |
C#
// C# program for the above approachusing System;using System.Collections.Generic; class GFG{ // Function to find the minimum sum of // all the medians of the K sized sorted // arrays formed from the given array static void sumOfMedians(int[] arr, int N, int K) { // Stores the distance between // the medians int selectMedian = (K + 1) / 2; // Stores the number of subsequences // required int totalArrays = N / K; // Stores the resultant sum int minSum = 0; // Iterate from start and add // all the medians int i = selectMedian - 1; while (i < N && totalArrays != 0) { // Add the value of arr[i] // to the variable minsum minSum = minSum + arr[i]; // Increment i by select the // median to get the next // median index i = i + selectMedian; // Decrement the value of // totalArrays by 1 totalArrays--; } // Print the resultant minimum sum Console.WriteLine(minSum); } // Driver Codepublic static void Main(){ int[] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; int K = 2; sumOfMedians(arr, N, K); }}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript program for the above approach // Function to find the minimum sum of // all the medians of the K sized sorted // arrays formed from the given array function sumOfMedians(arr, N, K) { // Stores the distance between // the medians let selectMedian = Math.floor((K + 1) / 2); // Stores the number of subsequences // required let totalArrays = Math.floor(N / K); // Stores the resultant sum let minSum = 0; // Iterate from start and add // all the medians let i = selectMedian - 1; while (i < N && totalArrays != 0) { // Add the value of arr[i] // to the variable minsum minSum = minSum + arr[i]; // Increment i by select the // median to get the next // median index i = i + selectMedian; // Decrement the value of // totalArrays by 1 totalArrays--; } // Print the resultant minimum sum document.write(minSum); }// Driver Code let arr = [ 1, 2, 3, 4, 5, 6 ]; let N = arr.length; let K = 2; sumOfMedians(arr, N, K); </script> |
Output:
6
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
