Elemento común mínimo en todos los subarreglos de tamaño K

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros distintos y un entero positivo K , la tarea es encontrar el elemento mínimo que aparece en todos los subarreglos de tamaño K . Si no existe tal elemento, imprima “-1” .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 4
Salida: 2
Explicación:
Los subarreglos de tamaño 4 son {1, 2, 3, 4} y {2, 3, 4, 5 }. Los elementos comunes en los subarreglos anteriores son {2, 3, 4}.
El mínimo del elemento común anterior es 2.

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 2
Salida: -1
Explicación: 
Los subarreglos de tamaño 2 son {1, 2}, {2, 3}, {3, 4} , {4, 5}. Como no hay un elemento común, imprima -1.

Enfoque ingenuo: la idea es generar todos los subarreglos posibles del arreglo dado de tamaño K y encontrar los elementos comunes en todos los subarreglos formados. Después de encontrar los elementos comunes, imprime el mínimo entre ellos. Si no se encuentra ningún elemento común en todos los subarreglos, imprima «-1» . 

Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)

Enfoque eficiente: la idea es verificar primero la condición del elemento común en todos los subarreglos y, si dicho elemento existe, debería estar dentro del rango [N – K, K] , en el arreglo dado. A continuación se detallan las condiciones en las que podemos encontrar dicho elemento mínimo:

  • Si N es impar y K ≥ (N + 1)/2 .
  • Si N es par y K ≥ ((N + 1)/2) + 1 .

Si las condiciones anteriores no se cumplen, entonces el elemento mínimo se encuentra en el rango [N – K, K] . Por lo tanto, itere sobre la array dada en este rango e imprima el valor del elemento mínimo en él.

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 minimum common
// among all the subarray of size K
// from the given array arr[]
void minCommonElementInSubarrays(
    int arr[], int N, int K)
{
    int c;
 
    // If N is odd then update
    // C as K >= (N + 1)/2
    if ((N + 1) % 2 == 0) {
        c = (N + 1) / 2;
    }
 
    // If N is even then update
    // C as K >= (N + 1)/2 + 1
    else {
        c = (N + 1) / 2 + 1;
    }
 
    // If K < C, return "=1"
    if (K < c) {
        cout << -1;
    }
 
    // Otherwise
    else {
 
        // Initialize result variable
        int ar = INT_MAX;
 
        // Find minimum element
        for (int i = N - K; i < K; i++) {
            ar = min(arr[i], ar);
        }
 
        // Print the minimum value
        cout << ar;
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 2, 3, 4, 5 };
 
    // Given K
    int K = 4;
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    minCommonElementInSubarrays(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
   
// Function to find the minimum common
// among all the subarray of size K
// from the given array arr[]
static void minCommonElementInSubarrays(int arr[],
                                        int N, int K)
{
    int c;
   
    // If N is odd then update
    // C as K >= (N + 1)/2
    if ((N + 1) % 2 == 0)
    {
        c = (N + 1) / 2;
    }
   
    // If N is even then update
    // C as K >= (N + 1)/2 + 1
    else
    {
        c = (N + 1) / 2 + 1;
    }
   
    // If K < C, return "=1"
    if (K < c)
    {
        System.out.print(-1);
    }
   
    // Otherwise
    else
    {
         
        // Initialize result variable
        int ar = Integer.MAX_VALUE;
   
        // Find minimum element
        for(int i = N - K; i < K; i++)
        {
            ar = Math.min(arr[i], ar);
        }
   
        // Print the minimum value
        System.out.print(ar);
    }
}
   
// Driver Code
public static void main (String[] args)
{
     
    // Given array arr[]
    int arr[] = { 1, 2, 3, 4, 5 };
   
    // Given K
    int K = 4;
   
    int N = arr.length;
   
    // Function call
    minCommonElementInSubarrays(arr, N, K);
}
}
 
// This code is contributed by sanjoy_62

Python3

# Python3 program for the above approach
import sys
 
# Function to find the minimum common
# among all the subarray of size K
# from the given array arr[]
def minCommonElementInSubarrays(arr, N, K):
     
    c = 0
 
    # If N is odd then update
    # C as K >= (N + 1)/2
    if ((N + 1) % 2 == 0):
        c = (N + 1) // 2
 
    # If N is even then update
    # C as K >= (N + 1)/2 + 1
    else:
        c = (N + 1) / 2 + 1
 
    # If K < C, return "=1"
    if (K < c):
        print(-1)
 
    # Otherwise
    else:
         
        # Initialize result variable
        ar = sys.maxsize
 
        # Find minimum element
        for i in range(N - K, K):
            ar = min(arr[i], ar)
 
        # Print the minimum value
        print(ar)
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 1, 2, 3, 4, 5 ]
 
    # Given K
    K = 4
 
    N = len(arr)
 
    # Function call
    minCommonElementInSubarrays(arr, N, K)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
   
// Function to find the minimum common
// among all the subarray of size K
// from the given array arr[]
static void minCommonElementInSubarrays(int[] arr,
                                        int N, int K)
{
    int c;
   
    // If N is odd then update
    // C as K >= (N + 1)/2
    if ((N + 1) % 2 == 0)
    {
        c = (N + 1) / 2;
    }
   
    // If N is even then update
    // C as K >= (N + 1)/2 + 1
    else
    {
        c = (N + 1) / 2 + 1;
    }
   
    // If K < C, return "=1"
    if (K < c)
    {
        Console.Write(-1);
    }
   
    // Otherwise
    else
    {
         
        // Initialize result variable
        int ar = Int32.MaxValue;
   
        // Find minimum element
        for(int i = N - K; i < K; i++)
        {
            ar = Math.Min(arr[i], ar);
        }
         
        // Print the minimum value
        Console.Write(ar);
    }
}
   
// Driver Code
public static void Main ()
{
     
    // Given array arr[]
    int[] arr = { 1, 2, 3, 4, 5 };
   
    // Given K
    int K = 4;
   
    int N = arr.Length;
   
    // Function call
    minCommonElementInSubarrays(arr, N, K);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the minimum common
// among all the subarray of size K
// from the given array arr[]
function minCommonElementInSubarrays(arr, N, K)
{
    let c;
 
    // If N is odd then update
    // C as K >= (N + 1)/2
    if ((N + 1) % 2 == 0) {
        c = parseInt((N + 1) / 2);
    }
 
    // If N is even then update
    // C as K >= (N + 1)/2 + 1
    else {
        c = parseInt((N + 1) / 2) + 1;
    }
 
    // If K < C, return "=1"
    if (K < c) {
        document.write(-1);
    }
 
    // Otherwise
    else {
 
        // Initialize result variable
        let ar = Number.MAX_VALUE;
 
        // Find minimum element
        for (let i = N - K; i < K; i++) {
            ar = Math.min(arr[i], ar);
        }
 
        // Print the minimum value
        document.write(ar);
    }
}
 
// Driver Code
    // Given array arr[]
    let arr = [ 1, 2, 3, 4, 5 ];
 
    // Given K
    let K = 4;
 
    let N = arr.length;
 
    // Function Call
    minCommonElementInSubarrays(arr, N, K);
 
</script>
Producción: 

2

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por amartyabhattacharya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *