Dada una array arr[] que tiene N enteros y un entero K , la tarea es seleccionar K elementos de la array dada de modo que la suma de todos los valores sea positiva y el valor máximo entre K enteros sea el mínimo.
Ejemplos:
Entrada: arr[] = {10, -8, 5, -5, -2, 4, -1, 0, 11}, k = 4
Salida: 4
Explicación:
La array posible es {0, 4, -1, – 2} el elemento máximo es 4 que es el mínimo posible.
Entrada: arr[] = {-8, -5, -2, -4, -1}, k = 2
Salida: -1
Explicación:
No es posible seleccionar K elementos.
Enfoque: La idea es utilizar la técnica de dos punteros . A continuación se muestran los pasos:
- Ordenar la array dada.
- Seleccione el valor menos no negativo de la array anterior (digamos en el índice idx ) usando lower_bound() en C++ .
- Si no existe un valor positivo en una array dada, entonces la suma siempre es negativa y ninguno de los elementos K satisface la condición dada.
- Si existen enteros positivos entonces puede existir la posibilidad de seleccionar K elementos cuya suma sea positiva.
- Usando la técnica de dos punteros podemos encontrar K enteros cuya suma sea positiva como:
- Inicializa dos punteros izquierdo y derecho como (ind – 1) e ind respectivamente.
- Agregue el elemento en el índice izquierdo (que es negativo) si la suma actual + arr[izquierda] es mayor que 0 para minimizar el valor máximo entre K elementos seleccionados y disminuir la izquierda.
- De lo contrario, agregue un elemento en el índice a la derecha y actualice el valor máximo e incremente a la derecha.
- Disminuya K para cada uno de los pasos anteriores.
- Repita lo anterior hasta que K se convierta en cero , la izquierda sea menor que cero o la derecha llegue al final de la array.
- Si K se convierte en cero en cualquiera de los anteriores, imprima el valor máximo almacenado.
- De lo contrario, escriba «-1» .
A continuación se muestra la implementación del enfoque anterior:
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 array
pair<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 Code
int 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 approach
import java.util.*;
class GFG{
// Function to print the maximum from K
// selected elements of the array
static 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 Code
public 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 approach import sys # Function to find lower_bound def 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 array def 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 call ans = 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 approach
using System;
class GFG{
// Function to print the maximum from K
// selected elements of the array
static 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 Code
public 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 array
function 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>
Producción:
-1
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)