Valor más grande de K tal que tanto K como -K existen en Array en un rango de índice dado [L, R]

Dada una array , arr[] de N enteros y 2 enteros L y R , la tarea es devolver el entero más grande K mayor que 0 y L<=K<=R, de modo que ambos valores K y -K existan en la array arr [] . Si no existe tal entero, devuelve 0 . 

Ejemplos:

Aporte:N = 5, arr[] = {3, 2, -2, 5, -3}, L = 2, R = 3
Salida: 3
Explicación: El valor más grande de K en el rango [2, 3] tal que ambos K y -K existen en la array es 3 ya que 3 está presente en arr[0] y -3 está presente en arr[4].

Entrada: N = 4, arr[] = {1, 2, 3, -4}, L = 1, R = 4
Salida: 0

Enfoque: la idea es atravesar la array y agregar el elemento al Conjunto y, al mismo tiempo, verificar su negativo, es decir, arr[i]*-1 en el Conjunto. Si se encuentra, introdúzcalo en el vector possible[] . Siga los pasos a continuación para resolver el problema:

• Inicialice un unordered_set<int> s[] para almacenar los elementos.
• Inicializa un vector posible[] para almacenar las posibles respuestas.
• Iterar sobre el rango [0, N) usando la variable i y realizar los siguientes pasos:
  • Si -arr[i] está presente en el conjunto s[] , introduzca el valor abs(arr[i]) en el vector possible[].
  • De lo contrario, agregue el elemento arr[i] al conjunto s[].
• Inicialice una variable ans como 0 para almacenar la respuesta.
• Itere sobre el rango [0, tamaño) donde tamaño es el tamaño del vector posible [], usando la variable i y realice los siguientes pasos:
  • Si posible[i] es mayor que igual a L y menor que igual a R, entonces actualice el valor de ans como el máximo de ans o posible[i].
• Después de realizar los pasos anteriores, imprima el valor de ans como respuesta.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum value of K
int findMax(int N, int arr[], int L, int R)
{
 
    // Using a set to store the elements
    unordered_set<int> s;
 
    // Vector to store the possible answers
    vector<int> possible;
 
    // Store the answer
    int ans = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If set has it's negation,
        // check if it is max
        if (s.find(arr[i] * -1) != s.end())
            possible.push_back(abs(arr[i]));
        else
            s.insert(arr[i]);
    }
 
    // Find the maximum possible answer
    for (int i = 0; i < possible.size(); i++) {
        if (possible[i] >= L and possible[i] <= R)
            ans = max(ans, possible[i]);
    }
 
    return ans;
}
 
// Driver Code
int main()
{
 
    int arr[] = { 3, 2, -2, 5, -3 },
        N = 5, L = 2, R = 3;
 
    int max = findMax(N, arr, L, R);
 
    // Display the output
    cout << max << endl;
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
public class GFG
{
   
// Function to find the maximum value of K
static int findMax(int N, int []arr, int L, int R)
{
 
    // Using a set to store the elements
    HashSet<Integer> s = new HashSet<Integer>();
   
    // ArrayList to store the possible answers
    ArrayList<Integer> possible
            = new ArrayList<Integer>();
 
    // Store the answer
    int ans = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If set has it's negation,
        // check if it is max
        if (s.contains(arr[i] * -1))
            possible.add(Math.abs(arr[i]));
        else
            s.add(arr[i]);
    }
 
    // Find the maximum possible answer
    for (int i = 0; i < possible.size(); i++) {
        if (possible.get(i) >= L && possible.get(i) <= R) {
            ans = Math.max(ans, possible.get(i));
        }
    }
 
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
 
    int []arr = { 3, 2, -2, 5, -3 };
    int N = 5, L = 2, R = 3;
 
    int max = findMax(N, arr, L, R);
 
    // Display the output
    System.out.println(max);
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python3 program for the above approach
 
# Function to find the maximum value of K
def findMax(N, arr, L, R) :
 
    # Using a set to store the elements
    s = set();
 
    # Vector to store the possible answers
    possible = [];
 
    # Store the answer
    ans = 0;
 
    # Traverse the array
    for i in range(N) :
 
        # If set has it's negation,
        # check if it is max
        if arr[i] * -1 in s  :
            possible.append(abs(arr[i]));
        else :
            s.add(arr[i]);
 
    # Find the maximum possible answer
    for i in range(len(possible)) :
        if (possible[i] >= L and possible[i] <= R) :
            ans = max(ans, possible[i]);
 
    return ans;
 
# Driver Code
if __name__ ==  "__main__" :
 
    arr = [ 3, 2, -2, 5, -3 ];
    N = 5; L = 2; R = 3;
 
    Max = findMax(N, arr, L, R);
 
    # Display the output
    print(Max);
 
    # This code is contributed by Ankthon

// Java program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
public class GFG
{
// Function to find the maximum value of K
static int findMax(int N, int []arr, int L, int R)
{
 
    // Using a set to store the elements
    HashSet<int> s = new HashSet<int>();
   
    // ArrayList to store the possible answers
    ArrayList possible = new ArrayList();
 
    // Store the answer
    int ans = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If set has it's negation,
        // check if it is max
        if (s.Contains(arr[i] * -1))
            possible.Add(Math.Abs(arr[i]));
        else
            s.Add(arr[i]);
    }
 
    // Find the maximum possible answer
    for (int i = 0; i < possible.Count; i++) {
        if ((int)possible[i] >= L && (int)possible[i] <= R) {
            ans = Math.Max(ans, (int)possible[i]);
        }
    }
 
    return ans;
}
 
// Driver Code
public static void Main()
{
 
    int []arr = { 3, 2, -2, 5, -3 };
    int N = 5, L = 2, R = 3;
 
    int max = findMax(N, arr, L, R);
 
    // Display the output
    Console.Write(max);;
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the maximum value of K
        function findMax(N, arr, L, R) {
 
            // Using a set to store the elements
            let s = new Set();
 
            // Vector to store the possible answers
            let possible = [];
 
            // Store the answer
            let ans = 0;
 
            // Traverse the array
            for (let i = 0; i < N; i++) {
 
                // If set has it's negation,
                // check if it is max
                if (s.has(arr[i] * -1))
                    possible.push(Math.abs(arr[i]));
                else
                    s.add(arr[i]);
            }
 
            // Find the maximum possible answer
            for (let i = 0; i < possible.length; i++) {
                if (possible[i] >= L && possible[i] <= R)
                    ans = Math.max(ans, possible[i]);
            }
 
            return ans;
        }
 
        // Driver Code
        let arr = [3, 2, -2, 5, -3];
        let N = 5, L = 2, R = 3;
 
        let max = findMax(N, arr, L, R);
 
        // Display the output
        document.write(max + '<br');
 
    // This code is contributed by Potta Lokesh
    </script>

3

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