Select K elements from an array whose maximum value is minimized
Given an array arr[] having N integers and an integer K, the task is to select K elements from the given array such that the sum of all the values is positive and the maximum value among K integers is minimum.
Examples:
Input: arr[] = {10, -8, 5, -5, -2, 4, -1, 0, 11}, k = 4
Output: 4
Explanation:
Possible array is {0, 4, -1, -2} the maximum element is 4 which is the minimum possible.
Input: arr[] = {-8, -5, -2, -4, -1}, k = 2
Output: -1
Explanation:
Selecting K elements is not possible.
Approach: The idea is to use the Two Pointer Technique. Below are the steps:
- Sort the given array.
- Select the least non-negative value from the above array(say at index idx) using lower_bound() in C++.
- If a positive value doesn’t exist in a given array, then the sum is always negative and none of the K element satisfies the given condition.
- If there exist positive integers then there can be a possibility of selecting K elements whose sum is positive.
- By using two pointers technique we can find K integers whose sum is positive as:
- Initialize two pointers left and right as (ind – 1) and ind respectively.
- Add the element at index left(which is negative) if current sum + arr[left] is greater than 0 to minimize the maximum value among K selected elements and decrement the left.
- Else add an element at index right and update the maximum value and increment right.
- Decrement K for each of the above steps.
- Repeat the above till K becomes zero, left is less than zero, or right reaches the end of the array.
- If K becomes zero in any of the above then print the maximum value stored.
- Else print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the maximum from K// selected elements of the arraypair<int, bool>kthsmallestelement(vector<int> a, int n, int k){ // Sort the array sort(a.begin(), a.end()); // Apply Binary search for // first positive element int ind = lower_bound(a.begin(), a.end(), 0) - a.begin(); // Check if no element is positive if (ind == n - 1 && a[n - 1] < 0) return make_pair(INT_MAX, false); // Initialize pointers int left = ind - 1, right = ind; int sum = 0; // Iterate to select exactly K elements while (k--) { // Check if left pointer // is greater than 0 if (left >= 0 && sum + a[left] > 0) { // Update sum sum = sum + a[left]; // Decrement left left--; } else if (right < n) { // Update sum sum = sum + a[right]; // Increment right right++; } else return make_pair(INT_MAX, false); } // Return the answer return make_pair(a[right - 1], true);}// Driver Codeint main(){ // Given array arr[] vector<int> arr = { -8, -5, -2, -4, -1 }; int n = arr.size(); int k = 2; // Function Call pair<int, bool> ans = kthsmallestelement(arr, n, k); if (ans.second == false) cout << "-1" << endl; else cout << ans.first << endl;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to print the maximum from K// selected elements of the arraystatic int[] kthsmallestelement(int[] a, int n, int k){ // Sort the array Arrays.sort(a); // Apply Binary search for // first positive element int ind = lowerBound(a, 0, a.length, 0); // Check if no element is positive if (ind == n - 1 && a[n - 1] < 0) return new int[] { Integer.MAX_VALUE, 0 }; // Initialize pointers int left = ind - 1, right = ind; int sum = 0; // Iterate to select exactly K elements while (k-- > 0) { // Check if left pointer // is greater than 0 if (left >= 0 && sum + a[left] > 0) { // Update sum sum = sum + a[left]; // Decrement left left--; } else if (right < n) { // Update sum sum = sum + a[right]; // Increment right right++; } else return new int[] { Integer.MAX_VALUE, 0 }; } // Return the answer return new int[] { a[right - 1], 1 };}static int lowerBound(int[] numbers, int start, int length, int searchnum){ // If the number is not in the // list it will return -1 int answer = -1; // Starting point of the list start = 0; // Ending point of the list int end = length - 1; while (start <= end) { // Finding the middle point of the list int middle = (start + end) / 2; if (numbers[middle] == searchnum) { answer = middle; end = middle - 1; } else if (numbers[middle] > searchnum) end = middle - 1; else start = middle + 1; } if (answer == -1) answer = length; return answer;}// Driver Codepublic static void main(String[] args){ // Given array arr[] int[] arr = { -8, -5, -2, -4, -1 }; int n = arr.length; int k = 2; // Function call int[] ans = kthsmallestelement(arr, n, k); if (ans[1] == 0) System.out.print("-1" + "\n"); else System.out.print(ans[0] + "\n");}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above approachimport sys# Function to find lower_bounddef LowerBound(numbers, length, searchnum): # If the number is not in the # list it will return -1 answer = -1 # Starting point of the list start = 0 # Ending point of the list end = length - 1 while start <= end: # Finding the middle point of the list middle = (start + end) // 2 if numbers[middle] == searchnum: answer = middle end = middle - 1 elif numbers[middle] > searchnum: end = middle - 1 else: start = middle + 1 if(answer == -1): answer = length return answer# Function to print the maximum from K# selected elements of the arraydef kthsmallestelement(a, n, k): # Sort the array a.sort() # Apply Binary search for # first positive element ind = LowerBound(a, len(a), 0) # Check if no element is positive if (ind == n - 1 and a[n - 1] < 0): return make_pair(INT_MAX, False) # Initialize pointers left = ind - 1 right = ind sum = 0 # Iterate to select exactly K elements while (k > 0): k -= 1 # Check if left pointer # is greater than 0 if (left >= 0 and sum + a[left] > 0): # Update sum sum = sum + a[left] # Decrement left left -= 1 elif (right < n): # Update sum sum = sum + a[right] # Increment right right += 1 else: return [sys.maxsize, False] print(sys.maxsize) # Return the answer return [a[right - 1], True]# Driver Code# Given array arr[]arr = [ -8, -5, -2, -4, -1 ]n = len(arr)k = 2# Function callans = kthsmallestelement(arr, n, k)if (ans[1] == False): print(-1)else: print(ans[0])# This code is contributed by Sanjit_Prasad |
C#
// C# program for the above approachusing System;class GFG{// Function to print the maximum from K// selected elements of the arraystatic int[] kthsmallestelement(int[] a, int n, int k){ // Sort the array Array.Sort(a); // Apply Binary search for // first positive element int ind = lowerBound(a, 0, a.Length, 0); // Check if no element is positive if (ind == n - 1 && a[n - 1] < 0) return new int[] { int.MaxValue, 0 }; // Initialize pointers int left = ind - 1, right = ind; int sum = 0; // Iterate to select exactly K elements while (k-- > 0) { // Check if left pointer // is greater than 0 if (left >= 0 && sum + a[left] > 0) { // Update sum sum = sum + a[left]; // Decrement left left--; } else if (right < n) { // Update sum sum = sum + a[right]; // Increment right right++; } else return new int[] { int.MaxValue, 0 }; } // Return the answer return new int[] { a[right - 1], 1 };}static int lowerBound(int[] numbers, int start, int length, int searchnum){ // If the number is not in the // list it will return -1 int answer = -1; // Starting point of the list start = 0; // Ending point of the list int end = length - 1; while (start <= end) { // Finding the middle point of the list int middle = (start + end) / 2; if (numbers[middle] == searchnum) { answer = middle; end = middle - 1; } else if (numbers[middle] > searchnum) end = middle - 1; else start = middle + 1; } if (answer == -1) answer = length; return answer;}// Driver Codepublic static void Main(String[] args){ // Given array []arr int[] arr = { -8, -5, -2, -4, -1 }; int n = arr.Length; int k = 2; // Function call int[] ans = kthsmallestelement(arr, n, k); if (ans[1] == 0) Console.Write("-1" + "\n"); else Console.Write(ans[0] + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program implementation// of the approach// Function to print the maximum from K// selected elements of the arrayfunction kthsmallestelement(a, n, k){ // Sort the array a.sort(); // Apply Binary search for // first positive element let ind = lowerBound(a, 0, a.length, 0); // Check if no element is positive if (ind == n - 1 && a[n - 1] < 0) return [ Number.MAX_VALUE, 0 ]; // Initialize pointers let left = ind - 1, right = ind; let sum = 0; // Iterate to select exactly K elements while (k-- > 0) { // Check if left pointer // is greater than 0 if (left >= 0 && sum + a[left] > 0) { // Update sum sum = sum + a[left]; // Decrement left left--; } else if (right < n) { // Update sum sum = sum + a[right]; // Increment right right++; } else return [ Number.MAX_VALUE, 0 ]; } // Return the answer return [ a[right - 1], 1 ];} function lowerBound( numbers, start, length, searchnum){ // If the number is not in the // list it will return -1 let answer = -1; // Starting point of the list start = 0; // Ending point of the list let end = length - 1; while (start <= end) { // Finding the middle point of the list let middle = (start + end) / 2; if (numbers[middle] == searchnum) { answer = middle; end = middle - 1; } else if (numbers[middle] > searchnum) end = middle - 1; else start = middle + 1; } if (answer == -1) answer = length; return answer;}// Driver Code // Given array arr[] let arr = [ -8, -5, -2, -4, -1 ]; let n = arr.length; let k = 2; // Function call let ans = kthsmallestelement(arr, n, k); if (ans[1] == 0) document.write("-1" + "\n"); else document.write(ans[0] + "\n"); </script> |
Output:
-1
Time Complexity: O(N * log 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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
