Dada una array arr[] que consta de N enteros y un entero K , la tarea es reducir K a 0 eliminando un elemento de array de cualquier extremo de la array y restándolo de K . Si es imposible reducir K a 0 , imprima “-1” . De lo contrario, imprima el número mínimo de tales operaciones requeridas.
Ejemplos:
Entrada: a rr[] = {1, 3, 1, 1, 2}, K = 4
Salida: 2
Explicación:
La array dada es {1, 3, 1, 1, 2}
Operación 1: Eliminar arr[0] ( = 1) modifica arr[] a {3, 1, 1, 2}. Restar arr[0] de K reduce K a 4 – 1 = 3.
Operación 2: Eliminar arr[0] (= 1) modifica arr[] a {1, 1, 2}. Restar arr[0] de K reduce K a 3 – 3 = 0.
Por lo tanto, el número total de pasos necesarios es 2.Entrada: arr[] = {1, 1, 3, 4}, K = 3
Salida: -1
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Considere que los elementos X e Y deben eliminarse del frente y la parte posterior de la array dada, respectivamente, para reducir K a 0 .
- Por lo tanto, la suma de los elementos restantes de la array debe ser igual a ( suma de los elementos de la array – K) .
Por lo tanto, a partir de la observación anterior, la idea es encontrar la longitud máxima del subarreglo (digamos L ) cuya suma sea igual a ( suma de los elementos del arreglo – K) . Por lo tanto, imprima el valor de (N – L) como el elemento mínimo resultante que debe eliminarse para reducir K a 0 . Si no existe tal subarreglo, imprima «-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 find the length of
// longest subarray having sum K
int longestSubarray(int arr[],
int N, int K)
{
// Stores the index of
// the prefix sum
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// Traverse the given array
for (int i = 0; i < N; i++) {
// Update sum
sum += arr[i];
// If the subarray starts
// from index 0
if (sum == K)
maxLen = i + 1;
// Add the current prefix sum
// with index if it is not
// present in the map um
if (um.find(sum) == um.end())
um[sum] = i;
// Check if sum - K is
// present in Map um or not
if (um.find(sum - K) != um.end()) {
// Update the maxLength
if (maxLen < (i - um[sum - K]))
maxLen = i - um[sum - K];
}
}
// Return the required maximum length
return maxLen;
}
// Function to find the minimum removal of
// array elements required to reduce K to 0
void minRequiredOperation(int arr[],
int N, int K)
{
// Stores the sum of the array
int TotalSum = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
// Update sum of the array
TotalSum += arr[i];
// Find maxLen
int maxLen = longestSubarray(
arr, N, TotalSum - K);
// If the subarray with
// sum doesn't exist
if (maxLen == -1) {
cout << -1;
}
// Otherwise, print the
// required maximum length
else
cout << N - maxLen;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 1, 1, 2 };
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
minRequiredOperation(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the length of
// longest subarray having sum K
static int longestSubarray(int[] arr, int N, int K)
{
// Stores the index of
// the prefix sum
HashMap<Integer,
Integer> um = new HashMap<Integer,
Integer>();
int sum = 0, maxLen = 0;
// Traverse the given array
for(int i = 0; i < N; i++)
{
// Update sum
sum += arr[i];
// If the subarray starts
// from index 0
if (sum == K)
maxLen = i + 1;
// Add the current prefix sum
// with index if it is not
// present in the map um
if (!um.containsKey(sum))
um.put(sum, i);
// Check if sum - K is
// present in Map um or not
if (um.containsKey(sum - K))
{
// Update the maxLength
if (maxLen < (i - um.get(sum - K)))
maxLen = i - um.get(sum - K);
}
}
// Return the required maximum length
return maxLen;
}
// Function to find the minimum removal of
// array elements required to reduce K to 0
static void minRequiredOperation(int[] arr, int N,
int K)
{
// Stores the sum of the array
int TotalSum = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
// Update sum of the array
TotalSum += arr[i];
// Find maxLen
int maxLen = longestSubarray(arr, N, TotalSum - K);
// If the subarray with
// sum doesn't exist
if (maxLen == -1)
{
System.out.println(-1);
}
// Otherwise, print the
// required maximum length
else
System.out.println(N - maxLen);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 3, 1, 1, 2 };
int K = 4;
int N = arr.length;
minRequiredOperation(arr, N, K);
}
}
// This code is contributed by ukasp
Python3
# Python3 program for the above approach
# Function to find the length of
# longest subarray having sum K
def longestSubarray(arr, N, K):
# Stores the index of
# the prefix sum
um = {}
sum , maxLen = 0, 0
# Traverse the given array
for i in range(N):
# Update sum
sum += arr[i]
# If the subarray starts
# from index 0
if (sum == K):
maxLen = i + 1
# Add the current prefix sum
# with index if it is not
# present in the map um
if (sum not in um):
um[sum] = i
# Check if sum - K is
# present in Map um or not
if ((sum - K) in um):
# Update the maxLength
if (maxLen < (i - um[sum - K])):
maxLen = i - um[sum - K]
# Return the required maximum length
return maxLen
# Function to find the minimum removal of
# array elements required to reduce K to 0
def minRequiredOperation(arr, N, K):
# Stores the sum of the array
TotalSum = 0
# Traverse the array arr[]
for i in range(N):
# Update sum of the array
TotalSum += arr[i]
# Find maxLen
maxLen = longestSubarray(arr, N, TotalSum - K)
# If the subarray with
# sum doesn't exist
if (maxLen == -1):
print (-1,end="")
# Otherwise, print the
# required maximum length
else:
print (N - maxLen,end="")
# Driver Code
if __name__ == '__main__':
arr = [1, 3, 1, 1, 2]
K = 4
N = len(arr)
minRequiredOperation(arr, N, K)
# this code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the length of
// longest subarray having sum K
static int longestSubarray(int []arr,
int N, int K)
{
// Stores the index of
// the prefix sum
Dictionary<int,int> um = new Dictionary<int,int>();
int sum = 0, maxLen = 0;
// Traverse the given array
for (int i = 0; i < N; i++) {
// Update sum
sum += arr[i];
// If the subarray starts
// from index 0
if (sum == K)
maxLen = i + 1;
// Add the current prefix sum
// with index if it is not
// present in the map um
if (!um.ContainsKey(sum))
um[sum] = i;
// Check if sum - K is
// present in Map um or not
if (um.ContainsKey(sum - K)) {
// Update the maxLength
if (maxLen < (i - um[sum - K]))
maxLen = i - um[sum - K];
}
}
// Return the required maximum length
return maxLen;
}
// Function to find the minimum removal of
// array elements required to reduce K to 0
static void minRequiredOperation(int []arr,
int N, int K)
{
// Stores the sum of the array
int TotalSum = 0;
// Traverse the array arr[]
for (int i = 0; i < N; i++)
// Update sum of the array
TotalSum += arr[i];
// Find maxLen
int maxLen = longestSubarray(
arr, N, TotalSum - K);
// If the subarray with
// sum doesn't exist
if (maxLen == -1) {
Console.WriteLine(-1);
}
// Otherwise, print the
// required maximum length
else
Console.WriteLine(N - maxLen);
}
// Driver Code
public static void Main()
{
int []arr = { 1, 3, 1, 1, 2 };
int K = 4;
int N = arr.Length;
minRequiredOperation(arr, N, K);
}
}
// This code is contributed by SUREDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to find the length of
// longest subarray having sum K
function longestSubarray(arr, N, K)
{
// Stores the index of
// the prefix sum
let um = new Map();
let sum = 0, maxLen = 0;
// Traverse the given array
for(let i = 0; i < N; i++)
{
// Update sum
sum += arr[i];
// If the subarray starts
// from index 0
if (sum == K)
maxLen = i + 1;
// Add the current prefix sum
// with index if it is not
// present in the map um
if (!um.has(sum))
um.set(sum, i);
// Check if sum - K is
// present in Map um or not
if (um.has(sum - K))
{
// Update the maxLength
if (maxLen < (i - um.get(sum - K)))
maxLen = i - um.get(sum - K);
}
}
// Return the required maximum length
return maxLen;
}
// Function to find the minimum removal of
// array elements required to reduce K to 0
function minRequiredOperation(arr, N, K)
{
// Stores the sum of the array
let TotalSum = 0;
// Traverse the array arr[]
for(let i = 0; i < N; i++)
// Update sum of the array
TotalSum += arr[i];
// Find maxLen
let maxLen = longestSubarray(
arr, N, TotalSum - K);
// If the subarray with
// sum doesn't exist
if (maxLen == -1)
{
document.write(-1);
}
// Otherwise, print the
// required maximum length
else
document.write(N - maxLen);
}
// Driver Code
let arr = [ 1, 3, 1, 1, 2 ];
let K = 4;
let N = arr.length
minRequiredOperation(arr, N, K);
// This code is contributed by gfgking
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)