Given an array arr[] of size N, the task is to find the minimum possible sum by extracting the smallest element from any K subsequences from arr[] of length L such that each of the subsequences have no shared element. If it is not possible to get the required sum, print -1.
Examples:
Input: arr[] = {2, 15, 5, 1, 35, 16, 67, 10}, K = 3, L = 2
Output: 8
Explanation:
Three subsequences of length 2 can be {1, 35}, {2, 15}, {5, 16}
Minimum element of {1, 35} is 1.
Minimum element of {2, 15} is 2.
Minimum element of {5, 16} is 5.
Their Sum is equal to 8 which is the minimum possible.Input: arr[] = {19, 11, 21, 16, 22, 18, 14, 12}, K = 3, L = 3
Output: -1
Explanation:
It is not possible to construct 3 subsequences of length 3 from arr[].
Approach:
To optimize the above approach, we need to observe the following details:
- The K smallest elements of the array contribute to finding the minimum sum of the smallest elements of K subsequences.
- The length of the array must be greater than or equal to (K * L) in order to form K subsequences of length L.
Follow the steps below to solve the problem:
- Check if the size of the array arr[] is greater than equal to (K * L).
- If so, sort the array arr[] and print the sum of the first K elements of the array after sorting.
- Otherwise, return -1.
Below is the implementation of the above approach:
C++
// C++ Program to find the minimum // possible sum of the smallest // elements from K subsequences #include <bits/stdc++.h> using namespace std; // Function to find the minimum sum int findMinSum(int arr[], int K, int L, int size) { if (K * L > size) return -1; int minsum = 0; // Sort the array sort(arr, arr + size); // Calculate sum of smallest // K elements for (int i = 0; i < K; i++) minsum += arr[i]; // Return the sum return minsum; } // Driver Code int main() { int arr[] = { 2, 15, 5, 1, 35, 16, 67, 10 }; int K = 3; int L = 2; int length = sizeof(arr) / sizeof(arr[0]); cout << findMinSum(arr, K, L, length); return 0; } |
Java
// Java program to find the minimum// possible sum of the smallest// elements from K subsequencesimport java.util.Arrays;class GFG{// Function to find the minimum sumstatic int findMinSum(int []arr, int K, int L, int size){ if (K * L > size) return -1; int minsum = 0; // Sort the array Arrays.sort(arr); // Calculate sum of smallest // K elements for(int i = 0; i < K; i++) minsum += arr[i]; // Return the sum return minsum;}// Driver Codepublic static void main(String args[]) { int arr[] = { 2, 15, 5, 1, 35, 16, 67, 10 }; int K = 3; int L = 2; int length = arr.length; System.out.print(findMinSum(arr, K, L, length));}}// This code is contributed by Ritik Bansal |
Python3
# Python3 program to find the minimum# possible sum of the smallest# elements from K subsequences# Function to find the minimum sumdef findMinSum(arr, K, L, size): if (K * L > size): return -1 minsum = 0 # Sort the array arr.sort() # Calculate sum of smallest # K elements for i in range(K): minsum += arr[i] # Return the sum return minsum# Driver codeif __name__ == '__main__': arr = [2, 15, 5, 1, 35, 16, 67, 10] K = 3 L = 2 length = len(arr) print(findMinSum(arr, K, L, length))# This code is contributed by Shivam Singh |
C#
// C# program to find the minimum // possible sum of the smallest // elements from K subsequences using System; class GFG{ // Function to find the minimum sum static int findMinSum(int []arr, int K, int L, int size) { if (K * L > size) return -1; int minsum = 0; // Sort the array Array.Sort(arr); // Calculate sum of smallest // K elements for(int i = 0; i < K; i++) minsum += arr[i]; // Return the sum return minsum; } // Driver Code public static void Main() { int[] arr = { 2, 15, 5, 1, 35, 16, 67, 10 }; int K = 3; int L = 2; int length = arr.Length; Console.Write(findMinSum(arr, K, L, length)); } } // This code is contributed by code_hunt |
Javascript
<script>// Javascript program to find the minimum// possible sum of the smallest// elements from K subsequences// Function to find the minimum sumfunction findMinSum(arr, K, L, size){ if (K * L > size) return -1; let minsum = 0; // Sort the array arr.sort((a, b) => a - b); // Calculate sum of smallest // K elements for(let i = 0; i < K; i++) minsum += arr[i]; // Return the sum return minsum;} // Driver Code let arr = [ 2, 15, 5, 1, 35, 16, 67, 10 ]; let K = 3; let L = 2; let length = arr.length; document.write(findMinSum(arr, K, L, length));</script> |
8
Time Complexity: O(N * log(N))
Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
