Dada una array arr[] de longitud N, la tarea es encontrar el producto mínimo del subarreglo de tamaño K de una array que incluye enteros negativos.
Ejemplo:
Entrada: arr = [2, 3, -1, -5, 4, 0], K = 3
Salida: -6
Explicación: El producto del subarreglo {2, 3, -1} es -6 que es el mínimo posible .Entrada: arr = [-2, -4, 0, 1, 5, -6, 9], K =4
Salida: -270
Explicación: El producto del subarreglo {1, 5, -6, 9} es -270 que es lo mínimo posible.
Si la array consta solo de números positivos, el problema se puede resolver de manera eficiente usando solo la técnica de la ventana deslizante, como se explica aquí .
Enfoque: El problema dado se puede resolver utilizando la técnica de dos punteros y el enfoque de ventana deslizante . Se pueden seguir los siguientes pasos para resolver el problema:
- Itere el arreglo arr hasta K – 1 y multiplique cada número distinto de cero para encontrar el producto y también cuente el número de ceros en el subarreglo.
- Itere la array arr desde K hasta el final de la array y en cada iteración:
- Si el elemento actual no es un cero, multiplíquelo al producto o incremente el conteo de ceros.
- Si el elemento a la izquierda de la ventana deslizante actual no es un cero, divida el producto por ese elemento o reduzca la cuenta de ceros.
- Si el número de ceros en la ventana deslizante es 0, actualice el resultado con el producto actual o actualícelo con cero
- Devuelve el resultado res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// product of subarray of size K
int minProdK(vector<int>& arr, int K)
{
// Initialize prod to 1
// and zeros to 0
int prod = 1, zeros = 0;
// Initialize length of the array
int N = arr.size();
// Iterate the array arr till K - 1
for (int i = 0; i < K; i++) {
// If current element is 0
// then increment zeros
if (arr[i] == 0)
zeros++;
// Else multiply current
// element to prod
else
prod *= arr[i];
}
// Initialize prod to 0 if zeros > 0
// else to prod
int res = zeros == 0 ? prod : 0;
// Iterate the array arr
// from K till the end
for (int right = K; right < N; right++) {
// If current element is 0
// then increment zeros
if (arr[right] == 0)
zeros++;
// Else multiply arr[right]
// to prod
else
prod *= arr[right];
// If leftmost element in
// the sliding window is 0
// then decrement zeros
if (arr[right - K] == 0)
zeros--;
// Else divide prod by arr[right-K]
else
prod /= arr[right - K];
// If zeros == 0 then update
// res by taking minimum value
// of res and prod
if (zeros == 0)
res = min(res, prod);
// If zeros > 0 and res > 0
// then initialize res to 0
else if (res > 0)
res = 0;
}
// Return the answer as res
return res;
}
// Driver code
int main()
{
// Initialize the array
vector<int> arr = { 2, 3, -1, -5, 4, 0 };
// Initialize the value of K
int K = 3;
// Call the function and
// print the result
cout << minProdK(arr, K);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the minimum
// product of subarray of size K
public static int minProdK(
int arr[], int K)
{
// Initialize prod to 1
// and zeros to 0
int prod = 1, zeros = 0;
// Initialize length of the array
int N = arr.length;
// Iterate the array arr till K - 1
for (int i = 0; i < K; i++) {
// If current element is 0
// then increment zeros
if (arr[i] == 0)
zeros++;
// Else multiply current
// element to prod
else
prod *= arr[i];
}
// Initialize prod to 0 if zeros > 0
// else to prod
int res = zeros == 0 ? prod : 0;
// Iterate the array arr
// from K till the end
for (int right = K; right < N; right++) {
// If current element is 0
// then increment zeros
if (arr[right] == 0)
zeros++;
// Else multiply arr[right]
// to prod
else
prod *= arr[right];
// If leftmost element in
// the sliding window is 0
// then decrement zeros
if (arr[right - K] == 0)
zeros--;
// Else divide prod by arr[right-K]
else
prod /= arr[right - K];
// If zeros == 0 then update
// res by taking minimum value
// of res and prod
if (zeros == 0)
res = Math.min(res, prod);
// If zeros > 0 and res > 0
// then initialize res to 0
else if (res > 0)
res = 0;
}
// Return the answer as res
return res;
}
// Driver code
public static void main(String[] args)
{
// Initialize the array
int[] arr = { 2, 3, -1, -5, 4, 0 };
// Initialize the value of K
int K = 3;
// Call the function and
// print the result
System.out.println(minProdK(arr, K));
}
}
Python3
# Python 3 implementation for the above approach # Function to find the minimum # product of subarray of size K def minProdK(arr, K): # Initialize prod to 1 # and zeros to 0 prod = 1 zeros = 0 # Initialize length of the array N = len(arr) # Iterate the array arr till K - 1 for i in range(K): # If current element is 0 # then increment zeros if (arr[i] == 0): zeros += 1 # Else multiply current # element to prod else: prod *= arr[i] # Initialize prod to 0 if zeros > 0 # else to prod if zeros == 0: res = prod else: res = 0 # Iterate the array arr # from K till the end for right in range(K, N): # If current element is 0 # then increment zeros if (arr[right] == 0): zeros += 1 # Else multiply arr[right] # to prod else: prod *= arr[right] # If leftmost element in # the sliding window is 0 # then decrement zeros if (arr[right - K] == 0): zeros -= 1 # Else divide prod by arr[right-K] else: prod //= arr[right - K] # If zeros == 0 then update # res by taking minimum value # of res and prod if (zeros == 0): res = min(res, prod) # If zeros > 0 and res > 0 # then initialize res to 0 elif (res > 0): res = 0 # Return the answer as res return res # Driver code if __name__ == "__main__": # Initialize the array arr = [2, 3, -1, -5, 4, 0] # Initialize the value of K K = 3 # Call the function and # print the result print(minProdK(arr, K)) # This code is contributed by ukasp.
C#
// C# implementation for the above approach
using System;
class GFG
{
// Function to find the minimum
// product of subarray of size K
public static int minProdK(
int []arr, int K)
{
// Initialize prod to 1
// and zeros to 0
int prod = 1, zeros = 0;
// Initialize length of the array
int N = arr.Length;
// Iterate the array arr till K - 1
for (int i = 0; i < K; i++) {
// If current element is 0
// then increment zeros
if (arr[i] == 0)
zeros++;
// Else multiply current
// element to prod
else
prod *= arr[i];
}
// Initialize prod to 0 if zeros > 0
// else to prod
int res = zeros == 0 ? prod : 0;
// Iterate the array arr
// from K till the end
for (int right = K; right < N; right++) {
// If current element is 0
// then increment zeros
if (arr[right] == 0)
zeros++;
// Else multiply arr[right]
// to prod
else
prod *= arr[right];
// If leftmost element in
// the sliding window is 0
// then decrement zeros
if (arr[right - K] == 0)
zeros--;
// Else divide prod by arr[right-K]
else
prod /= arr[right - K];
// If zeros == 0 then update
// res by taking minimum value
// of res and prod
if (zeros == 0)
res = Math.Min(res, prod);
// If zeros > 0 and res > 0
// then initialize res to 0
else if (res > 0)
res = 0;
}
// Return the answer as res
return res;
}
// Driver code
public static void Main()
{
// Initialize the array
int[] arr = { 2, 3, -1, -5, 4, 0 };
// Initialize the value of K
int K = 3;
// Call the function and
// print the result
Console.Write(minProdK(arr, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript implementation for the above approach
// Function to find the minimum
// product of subarray of size K
function minProdK(arr, K) {
// Initialize prod to 1
// and zeros to 0
let prod = 1, zeros = 0;
// Initialize length of the array
let N = arr.length;
// Iterate the array arr till K - 1
for (let i = 0; i < K; i++) {
// If current element is 0
// then increment zeros
if (arr[i] == 0)
zeros++;
// Else multiply current
// element to prod
else
prod *= arr[i];
}
// Initialize prod to 0 if zeros > 0
// else to prod
let res = zeros == 0 ? prod : 0;
// Iterate the array arr
// from K till the end
for (let right = K; right < N; right++) {
// If current element is 0
// then increment zeros
if (arr[right] == 0)
zeros++;
// Else multiply arr[right]
// to prod
else
prod *= arr[right];
// If leftmost element in
// the sliding window is 0
// then decrement zeros
if (arr[right - K] == 0)
zeros--;
// Else divide prod by arr[right-K]
else
prod /= arr[right - K];
// If zeros == 0 then update
// res by taking minimum value
// of res and prod
if (zeros == 0)
res = Math.min(res, prod);
// If zeros > 0 and res > 0
// then initialize res to 0
else if (res > 0)
res = 0;
}
// Return the answer as res
return res;
}
// Driver code
// Initialize the array
let arr = [2, 3, -1, -5, 4, 0];
// Initialize the value of K
let K = 3;
// Call the function and
// print the result
document.write(minProdK(arr, K));
// This code is contributed by Saurabh Jaiswal
</script>
Producción
-6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rajakbiswajit409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA