Dada una array arr[] de enteros positivos de tamaño N y un entero K. La tarea es minimizar el número de operaciones requeridas, elegir elementos de la array que sumen K. En una operación, un elemento se puede quitar desde el frente , o desde la parte posterior , o desde el frente y la parte posterior, y agregarlo a la suma . . Si no se puede lograr la suma deseada, devuelva -1 .
Ejemplo:
Entrada: arr[] = {3, 5, 4, 2, 1}, N = 5, K = 6
Salida: 2
Explicación:
- En la operación 1, visita los índices 0 y 4, elige ambos elementos (3 y 1), sumando así 3 + 1 = 4
- En la operación 2, visita el índice 3 (elemento 2), sumando así 4 + 2 = 6.
Entonces, operaciones mínimas requeridas = 2
Entrada: arr[] = {4, 7, 2, 3, 1, 9, 8}, N = 6, K = 9
Salida: 3
Enfoque: siga los pasos a continuación para resolver el problema:
- Cree un mapa y tome dos variables, digamos m1 y m2 para máximos locales y mínimos globales respectivamente.
- Atraviese la array y verifique las siguientes condiciones:
- Si el elemento es mayor o igual que k , entonces continúe, porque no puede generar k cuando se suma a cualquier otro elemento, ya que todos los elementos son mayores que cero .
- Si el elemento es exactamente la mitad de k , continúe también porque aquí, la tarea es encontrar dos elementos distintos .
- Si la posición en el mapa ya está llena, es decir, si el mismo elemento se encontró antes, verifique si estaba más cerca de algún extremo o si este nuevo elemento está más cerca y actualice el valor con esa clave , de lo contrario, simplemente verifique de qué extremo es acercar el elemento y ponerlo en el mapa .
- Si se encuentra un elemento que se llenó anteriormente en el mapa y que hace la suma de k con el elemento actual, entonces el tiempo necesario para seleccionar ambos elementos será el máximo y m2 es el mínimo de todos los pares distintos que suman k donde cada par, cada número, ya se eligió de manera óptima , mientras se llenaba el mapa .
- Después de atravesar, verifique el valor de m2 . Si m2 sigue siendo INT_MAX , devuelva -1 , de lo contrario devuelva m2 .
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 find minimum time required
// to visit array elements to get the
// sum equal to k
int minimumTime(int arr[], int N, int k)
{
// Create a map
map<int, int> mp;
// m1 is to keep the local maxima
int m1 = 0;
// m2 is to keep the global minima
int m2 = INT_MAX;
// Traverse the array
for (int i = 0; i < N; i++) {
// If the element is greater than
// or equal to k then continue
if (arr[i] >= k)
continue;
// If the element is exactly the
// half of k, then also continue
if (arr[i] == k / 2 && k - arr[i] == k / 2)
continue;
// If the position at the map is already filled,
// i.e if the same element was found earlier
// then check if that was nearer to any end
// or this new element is nearer and update
// the value with that key, else check from
// which end is the element closer and put it
// in the map
mp[arr[i]] = mp[arr[i]] ? min(mp[arr[i]],
min(i + 1, N - i))
: min(i + 1, N - i);
// If an element is found which was filled
// earlier in the map, which makes the sum
// to k with the current element then the
// time taken will be maximum of picking
// both elements because it is visited
// simultaneously
if (mp[k - arr[i]]) {
m1 = max(mp[arr[i]], mp[k - arr[i]]);
// m2 is the minimal of all such distinct
// pairs that sum to k where in each pair
// each number was optimally chosen already
// while filling the map
m2 = min(m1, m2);
}
}
// If m2 is still INT_MAX, then there is no such pair
// else return the minimum time
return m2 != INT_MAX ? m2 : -1;
}
// Driver Code
int main()
{
int arr[] = { 4, 7, 2, 3, 1, 9, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 6;
cout << minimumTime(arr, N, K);
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <limits.h>
int min(int a, int b)
{
return (a < b) ? a : b;
}
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Function to find minimum time required
// to visit array elements to get the
// sum equal to k
int minimumTime(int arr[], int N, int k)
{
// Create a map
int mp[k + 1];
// m1 is to keep the local maxima
int m1 = 0;
// m2 is to keep the global minima
int m2 = INT_MAX;
// Traverse the array
for (int i = 0; i < N; i++)
{
// If the element is greater than
// or equal to k then continue
if (arr[i] >= k)
continue;
// If the element is exactly the
// half of k, then also continue
if (arr[i] == k / 2 && k - arr[i] == k / 2)
continue;
// If the position at the map is already filled,
// i.e if the same element was found earlier
// then check if that was nearer to any end
// or this new element is nearer and update
// the value with that key, else check from
// which end is the element closer and put it
// in the map
mp[arr[i]] = mp[arr[i]] ? min(mp[arr[i]],
min(i + 1, N - i))
: min(i + 1, N - i);
// If an element is found which was filled
// earlier in the map, which makes the sum
// to k with the current element then the
// time taken will be maximum of picking
// both elements because it is visited
// simultaneously
if (mp[k - arr[i]])
{
m1 = max(mp[arr[i]], mp[k - arr[i]]);
// m2 is the minimal of all such distinct
// pairs that sum to k where in each pair
// each number was optimally chosen already
// while filling the map
m2 = min(m1, m2);
}
}
// If m2 is still INT_MAX, then there is no such pair
// else return the minimum time
return m2 != INT_MAX ? m2 : -1;
}
int main()
{
int arr[] = {4, 7, 2, 3, 1, 9, 8};
int N = sizeof(arr) / sizeof(arr[0]);
int K = 6;
printf("%d", minimumTime(arr, N, K));
return 0;
}
// This code is contributed by abhinavprkash.
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find minimum time required
// to visit array elements to get the
// sum equal to k
static int minimumTime(int arr[], int N, int k)
{
// Create a map
HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
// m1 is to keep the local maxima
int m1 = 0;
// m2 is to keep the global minima
int m2 = Integer.MAX_VALUE;
// Traverse the array
for (int i = 0; i < N; i++) {
// If the element is greater than
// or equal to k then continue
if (arr[i] >= k)
continue;
// If the element is exactly the
// half of k, then also continue
if (arr[i] == k / 2 && k - arr[i] == k / 2)
continue;
// If the position at the map is already filled,
// i.e if the same element was found earlier
// then check if that was nearer to any end
// or this new element is nearer and update
// the value with that key, else check from
// which end is the element closer and put it
// in the map
if(mp.containsKey(arr[i]))
mp.put(arr[i], Math.min(mp.get(arr[i]),
Math.min(i + 1, N - i)));
else
mp.put(arr[i], Math.min(i + 1, N - i));
// If an element is found which was filled
// earlier in the map, which makes the sum
// to k with the current element then the
// time taken will be maximum of picking
// both elements because it is visited
// simultaneously
if (mp.containsKey(k - arr[i])) {
m1 = Math.max(mp.get(arr[i]), mp.get(k-arr[i]));
// m2 is the minimal of all such distinct
// pairs that sum to k where in each pair
// each number was optimally chosen already
// while filling the map
m2 = Math.min(m1, m2);
}
}
// If m2 is still Integer.MAX_VALUE, then there is no such pair
// else return the minimum time
return m2 != Integer.MAX_VALUE ? m2 : -1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 7, 2, 3, 1, 9, 8 };
int N = arr.length;
int K = 6;
System.out.print(minimumTime(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python Program to implement
# the above approach
# Function to find minimum time required
# to visit array elements to get the
# sum equal to k
def minimumTime(arr, N, k):
# Create a map
mp = {}
# m1 is to keep the local maxima
m1 = 0
# m2 is to keep the global minima
m2 = 10 ** 9
# Traverse the array
for i in range(N):
# If the element is greater than
# or equal to k then continue
if (arr[i] >= k):
continue
# If the element is exactly the
# half of k, then also continue
if (arr[i] == k // 2 and k - arr[i] == k // 2):
continue
# If the position at the map is already filled,
# i.e if the same element was found earlier
# then check if that was nearer to any end
# or this new element is nearer and update
# the value with that key, else check from
# which end is the element closer and put it
# in the map
if (arr[i] not in mp):
mp[arr[i]] = min(i + 1, N - i)
else:
mp[arr[i]] = min( mp[arr[i]], min(i + 1, N - i))
# If an element is found which was filled
# earlier in the map, which makes the sum
# to k with the current element then the
# time taken will be maximum of picking
# both elements because it is visited
# simultaneously
if ((k - arr[i]) in mp):
m1 = max(mp[arr[i]], mp[k - arr[i]])
# m2 is the minimal of all such distinct
# pairs that sum to k where in each pair
# each number was optimally chosen already
# while filling the map
m2 = min(m1, m2)
# If m2 is still INT_MAX, then there is no such pair
# else return the minimum time
return m2 if m2 != 10**9 else -1
# Driver Code
arr = [4, 7, 2, 3, 1, 9, 8]
N = len(arr)
K = 6
print(minimumTime(arr, N, K))
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find minimum time required
// to visit array elements to get the
// sum equal to k
static int minimumTime(int[] arr, int N, int k)
{
// Create a map
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// m1 is to keep the local maxima
int m1 = 0;
// m2 is to keep the global minima
int m2 = Int32.MaxValue;
// Traverse the array
for(int i = 0; i < N; i++)
{
// If the element is greater than
// or equal to k then continue
if (arr[i] >= k)
continue;
// If the element is exactly the
// half of k, then also continue
if (arr[i] == k / 2 && k - arr[i] == k / 2)
continue;
// If the position at the map is already filled,
// i.e if the same element was found earlier
// then check if that was nearer to any end
// or this new element is nearer and update
// the value with that key, else check from
// which end is the element closer and put it
// in the map
if (mp.ContainsKey(arr[i]))
mp[arr[i]] = Math.Min(
mp[arr[i]], Math.Min(i + 1, N - i));
else
mp[arr[i]] = Math.Min(i + 1, N - i);
// If an element is found which was filled
// earlier in the map, which makes the sum
// to k with the current element then the
// time taken will be maximum of picking
// both elements because it is visited
// simultaneously
if (mp.ContainsKey(k - arr[i]))
{
m1 = Math.Max(mp[arr[i]], mp[k - arr[i]]);
// m2 is the minimal of all such distinct
// pairs that sum to k where in each pair
// each number was optimally chosen already
// while filling the map
m2 = Math.Min(m1, m2);
}
}
// If m2 is still Integer.MAX_VALUE, then there is
// no such pair else return the minimum time
return m2 != Int32.MaxValue ? m2 : -1;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 4, 7, 2, 3, 1, 9, 8 };
int N = arr.Length;
int K = 6;
Console.WriteLine(minimumTime(arr, N, K));
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find minimum time required
// to visit array elements to get the
// sum equal to k
function minimumTime(arr, N, k)
{
// Create a map
let mp = new Map();
// m1 is to keep the local maxima
let m1 = 0;
// m2 is to keep the global minima
let m2 = Number.MAX_VALUE;
// Traverse the array
for (let i = 0; i < N; i++) {
// If the element is greater than
// or equal to k then continue
if (arr[i] >= k)
continue;
// If the element is exactly the
// half of k, then also continue
if (arr[i] == Math.floor(k / 2) && k - arr[i] == Math.floor(k / 2))
continue;
// If the position at the map is already filled,
// i.e if the same element was found earlier
// then check if that was nearer to any end
// or this new element is nearer and update
// the value with that key, else check from
// which end is the element closer and put it
// in the map
if (!mp.has(arr[i])) {
mp.set(arr[i], Math.min(i + 1, N - i))
}
else {
mp.set(arr[i], Math.min(mp.get(arr[i]), Math.min(i + 1, N - i)))
}
// If an element is found which was filled
// earlier in the map, which makes the sum
// to k with the current element then the
// time taken will be maximum of picking
// both elements because it is visited
// simultaneously
if (mp.has(k - arr[i])) {
m1 = Math.max(mp.get(arr[i]), mp.get(k - arr[i]));
// m2 is the minimal of all such distinct
// pairs that sum to k where in each pair
// each number was optimally chosen already
// while filling the map
m2 = Math.min(m1, m2);
}
}
// If m2 is still INT_MAX, then there is no such pair
// else return the minimum time
return m2 != Number.MAX_VALUE ? m2 : -1;
}
// Driver Code
let arr = [4, 7, 2, 3, 1, 9, 8];
let N = arr.length;
let K = 6;
document.write(minimumTime(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)