Dada una array nums[] y un entero X , la tarea es reducir X a 0 eliminando los elementos de la array más a la izquierda o más a la derecha y restando su valor de X, el número mínimo de veces. Si es posible reducir X a 0 , imprima el recuento de operaciones requeridas. De lo contrario, devuelve -1.
Ejemplos:
Entrada: nums[] = {3,2,20,1,1,3}, X = 10
Salida: 5
Explicación: X (= 10) – 3 – 1 – 1 – 3 – 2 = 0. Por lo tanto, el número de operaciones requeridas es 5.Entrada: nums[] = {1, 1, 4, 2, 3}, X = 5
Salida: 2
Explicación: X (= 5) – 3 – 2 = 0. Por lo tanto, el número de operaciones requeridas es 2.
Enfoque: El problema dado se puede resolver utilizando la técnica de dos punteros . Siga los pasos a continuación para resolver el problema.
- Mantenga dos punteros izquierdo y derecho, apuntando a los extremos de los subarreglos izquierdo y derecho excluidos de X.
- Inicialice hacia la izquierda para considerar la array completa y hacia la derecha para no incluir nada.
- Por lo tanto, reduce X por la suma de la array .
- Ahora, itere hasta que la izquierda llegue al frente de la array.
- Si la suma de los subarreglos izquierdo y derecho excede X ( es decir , X < 0 ), desplácese a la izquierda un índice hacia la izquierda y aumente X ese elemento.
- Si la suma de los subarreglos izquierdo y derecho es menor que X ( es decir , X > 0 ), mueva el puntero derecho un índice hacia la izquierda y reduzca X por ese elemento.
- Si se encuentra que X es 0 en cualquier punto, actualice el número mínimo de operaciones requeridas.
- Imprime el número mínimo de operaciones requeridas.
- A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the minimum
// number of operations required
// to reduce x to 0
static int minOperations(int nums[], int N,
int x)
{
// If sum of the array
// is less than x
int sum = 0;
for(int i = 0; i < x; i++)
sum += nums[i];
if (sum < x)
return -1;
// Stores the count
// of operations
int ans = INT_MAX;
// Two pointers to traverse the array
int l = N - 1, r = N;
// Reduce x by the sum
// of the entire array
x -= sum;
// Iterate until l reaches
// the front of the array
while (l >= 0)
{
// If sum of elements from
// the front exceeds x
if (x <= 0)
{
// Shift towards left
x += nums[l];
l -= 1;
}
// If sum exceeds 0
if (x > 0)
{
// Reduce x by elements
// from the right
r -= 1;
x -= nums[r];
}
// If x is reduced to 0
if (x == 0)
{
// Update the minimum count
// of operations required
ans = min(ans,
(l + 1) + (N - r));
}
}
if (ans < INT_MAX)
return ans;
else
return -1;
}
// Driver Code
int main()
{
int nums[] = { 1, 1, 4, 2, 3 };
// Size of the array
int N = sizeof(nums) / sizeof(nums[0]);
int x = 5;
cout << minOperations(nums, N, x);
return 0;
}
// This code is contributed by code_hunt
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to count the minimum
// number of operations required
// to reduce x to 0
static int minOperations(int nums[], int x)
{
// If sum of the array
// is less than x
int sum = 0;
for (int i = 0; i < x; i++)
sum += nums[i];
if (sum < x)
return -1;
// Stores the count
// of operations
int ans = Integer.MAX_VALUE;
// Two pointers to traverse the array
int l = nums.length - 1, r = nums.length;
// Reduce x by the sum
// of the entire array
x -= sum;
// Iterate until l reaches
// the front of the array
while (l >= 0) {
// If sum of elements from
// the front exceeds x
if (x <= 0) {
// Shift towards left
x += nums[l];
l -= 1;
}
// If sum exceeds 0
if (x > 0) {
// Reduce x by elements
// from the right
r -= 1;
x -= nums[r];
}
// If x is reduced to 0
if (x == 0) {
// Update the minimum count
// of operations required
ans = Math.min(ans,
(l + 1) + (nums.length - r));
}
}
if (ans < Integer.MAX_VALUE)
return ans;
else
return -1;
}
// Driver Code
public static void main(String[] args)
{
int[] nums = { 1, 1, 4, 2, 3 };
int x = 5;
System.out.println(minOperations(nums, x));
}
}
// This code is contributed by shubhamsingh10
Python3
# Python3 Program to implement # the above approach import math # Function to count the minimum # number of operations required # to reduce x to 0 def minOperations(nums, x): # If sum of the array # is less than x if sum(nums) < x: return -1 # Stores the count # of operations ans = math.inf # Two pointers to traverse the array l, r = len(nums)-1, len(nums) # Reduce x by the sum # of the entire array x -= sum(nums) # Iterate until l reaches # the front of the array while l >= 0: # If sum of elements from # the front exceeds x if x <= 0: # Shift towards left x += nums[l] l -= 1 # If sum exceeds 0 if x > 0: # Reduce x by elements # from the right r -= 1 x -= nums[r] # If x is reduced to 0 if x == 0: # Update the minimum count # of operations required ans = min(ans, (l+1) + (len(nums)-r)) return ans if ans < math.inf else -1 # Driver Code nums = [1, 1, 4, 2, 3] x = 5 print(minOperations(nums, x))
C#
// C# Program to implement
// the above approach
using System;
class GFG {
// Function to count the minimum
// number of operations required
// to reduce x to 0
static int minOperations(int[] nums, int x)
{
// If sum of the array
// is less than x
int sum = 0;
for (int i = 0; i < x; i++)
sum += nums[i];
if (sum < x)
return -1;
// Stores the count
// of operations
int ans = Int32.MaxValue;
// Two pointers to traverse the array
int l = nums.Length - 1, r = nums.Length;
// Reduce x by the sum
// of the entire array
x -= sum;
// Iterate until l reaches
// the front of the array
while (l >= 0) {
// If sum of elements from
// the front exceeds x
if (x <= 0) {
// Shift towards left
x += nums[l];
l -= 1;
}
// If sum exceeds 0
if (x > 0) {
// Reduce x by elements
// from the right
r -= 1;
x -= nums[r];
}
// If x is reduced to 0
if (x == 0) {
// Update the minimum count
// of operations required
ans = Math.Min(ans,
(l + 1) + (nums.Length - r));
}
}
if (ans < Int32.MaxValue)
return ans;
else
return -1;
}
// Driver Code
public static void Main()
{
int[] nums = { 1, 1, 4, 2, 3 };
int x = 5;
Console.Write(minOperations(nums, x));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to count the minimum
// number of operations required
// to reduce x to 0
function minOperations(nums, x)
{
// If sum of the array
// is less than x
let sum = 0;
for(let i = 0; i < x; i++)
sum += nums[i];
if (sum < x)
return -1;
// Stores the count
// of operations
let ans = Number.MAX_VALUE;
// Two pointers to traverse the array
let l = nums.length - 1, r = nums.length;
// Reduce x by the sum
// of the entire array
x -= sum;
// Iterate until l reaches
// the front of the array
while (l >= 0)
{
// If sum of elements from
// the front exceeds x
if (x <= 0)
{
// Shift towards left
x += nums[l];
l -= 1;
}
// If sum exceeds 0
if (x > 0)
{
// Reduce x by elements
// from the right
r -= 1;
x -= nums[r];
}
// If x is reduced to 0
if (x == 0)
{
// Update the minimum count
// of operations required
ans = Math.min(ans,
(l + 1) +
(nums.length - r));
}
}
if (ans < Number.MAX_VALUE)
return ans;
else
return -1;
}
// Driver code
let nums = [ 1, 1, 4, 2, 3 ];
let x = 5;
document.write(minOperations(nums, x));
// This code is contributed by target_2
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA