Dada una array arr[] que consta de N enteros, la tarea es encontrar el mayor número K ( > 0 ) tal que tanto los valores K como -K estén presentes en la array dada arr[] . Si no existe tal número, imprima -1 .
Ejemplos:
Entrada: arr[] = {3, 2, -2, 5, -3}
Salida: 3Entrada: arr[] = {1, 2, 3, -4}
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre la array y, para cada elemento, recorrer la array restante para verificar si su valor negativo existe en la array o no. Después de completar el recorrido de la array, imprima el número máximo obtenido.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de clasificación y dos punteros . Siga los pasos a continuación para resolver este problema:
- Inicializa una variable, digamos res como -1 que almacena el máximo elemento obtenido.
- Ordena la array dada arr[] .
- Inicialice dos variables, digamos l y r como 0 y (N – 1) , y realice los siguientes pasos:
- Si el valor de (arr[l] + arr[r]) es igual a 0 , devuelve el valor absoluto de arr[l] y arr[r] .
- De lo contrario, si el valor de (arr[l] + arr[r]) es menor que 0 , aumente el valor de l en 1 .
- De lo contrario, disminuya el valor de r en 1 .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
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 largest
// number k such that both k and
// -k are present in the array
int largestNum(vector<int>arr)
{
// Stores the resultant value
// of K
int res = 0;
// Sort the array arr[]
sort(arr.begin(), arr.end());
// Initialize two variables to
// use two pointers technique
int l = 0, r = arr.size() - 1;
// Iterate until the value of
// l is less than r
while (l < r)
{
// Find the value of the sum
int sum = arr[l] + arr[r];
// If the sum is 0, then the
// resultant element is found
if (sum == 0)
{
res = max(res, max(arr[l], arr[r]));
return res;
}
// If the sum is negative
else if (sum < 0)
{
l++;
}
// Otherwise, decrement r
else
{
r--;
}
}
return res;
}
// Driver Code
int main()
{
vector<int>arr = { 3, 2, -2, 5, -3 };
cout << (largestNum(arr));
}
// This code is contributed by amreshkumar3
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
public class GFG {
// Function to find the largest
// number k such that both k and
// -k are present in the array
public static int largestNum(int[] arr)
{
// Stores the resultant value
// of K
int res = 0;
// Sort the array arr[]
Arrays.sort(arr);
// Initialize two variables to
// use two pointers technique
int l = 0, r = arr.length - 1;
// Iterate until the value of
// l is less than r
while (l < r) {
// Find the value of the sum
int sum = arr[l] + arr[r];
// If the sum is 0, then the
// resultant element is found
if (sum == 0) {
res = Math.max(
res, Math.max(
arr[l], arr[r]));
return res;
}
// If the sum is negative
else if (sum < 0) {
l++;
}
// Otherwise, decrement r
else {
r--;
}
}
return res;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 3, 2, -2, 5, -3 };
System.out.println(
largestNum(arr));
}
}
Python3
# Python3 program for the above approach # Function to find the largest # number k such that both k and # -k are present in the array def largestNum(arr): # Stores the resultant value # of K res = 0 # Sort the array arr[] arr = sorted(arr) # Initialize two variables to # use two pointers technique l = 0 r = len(arr) - 1 # Iterate until the value of # l is less than r while (l < r): # Find the value of the sum sum = arr[l] + arr[r] # If the sum is 0, then the # resultant element is found if (sum == 0): res = max(res, max(arr[l], arr[r])) return res # If the sum is negative elif (sum < 0): l += 1 # Otherwise, decrement r else: r-=1 return res # Driver Code if __name__ == '__main__': arr =[3, 2, -2, 5, -3] print(largestNum(arr)) # 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 largest
// number k such that both k and
// -k are present in the array
static int largestNum(List<int>arr)
{
// Stores the resultant value
// of K
int res = 0;
// Sort the array arr[]
arr.Sort();
// Initialize two variables to
// use two pointers technique
int l = 0, r = arr.Count - 1;
// Iterate until the value of
// l is less than r
while (l < r)
{
// Find the value of the sum
int sum = arr[l] + arr[r];
// If the sum is 0, then the
// resultant element is found
if (sum == 0)
{
res = Math.Max(res, Math.Max(arr[l],
arr[r]));
return res;
}
// If the sum is negative
else if (sum < 0)
{
l++;
}
// Otherwise, decrement r
else
{
r--;
}
}
return res;
}
// Driver Code
public static void Main()
{
List<int>arr = new List<int>(){ 3, 2, -2, 5, -3 };
Console.Write(largestNum(arr));
}
}
// This code is contributed by bgangwar59
Javascript
<script>
// Javascript program for the above approach
// Function to find the largest
// number k such that both k and
// -k are present in the array
function largestNum(arr) {
// Stores the resultant value
// of K
let res = 0;
// Sort the array arr[]
arr.sort((a, b) => a - b);
// Initialize two variables to
// use two pointers technique
let l = 0, r = arr.length - 1;
// Iterate until the value of
// l is less than r
while (l < r) {
// Find the value of the sum
let sum = arr[l] + arr[r];
// If the sum is 0, then the
// resultant element is found
if (sum == 0) {
res = Math.max(res, Math.max(arr[l], arr[r]));
return res;
}
// If the sum is negative
else if (sum < 0) {
l++;
}
// Otherwise, decrement r
else {
r--;
}
}
return res;
}
// Driver Code
let arr = [3, 2, -2, 5, -3];
document.write((largestNum(arr)));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Enfoque optimizado: el enfoque anterior se puede optimizar aún más almacenando los elementos en un Conjunto . Siga los pasos a continuación para resolver este problema:
- Inicialice un conjunto S que almacene los elementos de la array.
- Inicialice una variable, diga res como -1 para almacenar el elemento máximo mientras recorre la array .
- Iterar sobre el rango [0, N – 1] usando la variable i y realizar los siguientes pasos:
- Agregue el elemento actual al conjunto S .
- Si el elemento está presente, actualice el valor de res al elemento actual.
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
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 largest
// number k such that both k and
// -k are present in the array
int largestNum(int arr[] ,int n)
{
// Stores the array elements
set<int> st;
// Initialize a variable res as
// 0 to store maximum element
// while traversing the array
int res = 0;
// Iterate through array arr
for(int i = 0; i < n; i++)
{
// Add the current element
// into the st
st.insert(arr[i]);
// Check if the negative of
// this element is also
// present in the st or not
if (st.find(-1 * arr[i]) != st.end())
{
res = max(res, abs(arr[i]));
}
}
// Return the resultant element
return res;
}
// Drive Code
int main()
{
int arr[] = { 3, 2, -2, 5, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << largestNum(arr, n);
}
// This code is contributed by SURENDRA_GANGWAR
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the largest
// number k such that both k and
// -k are present in the array
public static int largestNum(int[] arr)
{
// Stores the array elements
Set<Integer> set = new HashSet<>();
// Initialize a variable res as
// 0 to store maximum element
// while traversing the array
int res = 0;
// Iterate through array arr
for (int i = 0;
i < arr.length; i++) {
// Add the current element
// into the set
set.add(arr[i]);
// Check if the negative of
// this element is also
// present in the set or not
if (set.contains(-1 * arr[i])) {
res = Math.max(
res, Math.abs(arr[i]));
}
}
// Return the resultant element
return res;
}
// Drive Code
public static void
main(String[] args)
{
int[] arr = { 3, 2, -2, 5, -3 };
System.out.println(
largestNum(arr));
}
}
Python3
# Python3 program for the above approach # Function to find the largest # number k such that both k and # -k are present in the array def largestNum(arr, n) : # Stores the array elements st = set([]) # Initialize a variable res as # 0 to store maximum element # while traversing the array res = 0 # Iterate through array arr for i in range(n): # Add the current element # into the st st.add(arr[i]) # Check if the negative of # this element is also # present in the st or not if (-1 * arr[i]) in st: res = max(res, abs(arr[i])) # Return the resultant element return res arr = [ 3, 2, -2, 5, -3 ] n = len(arr) print(largestNum(arr, n)) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to find the largest
// number k such that both k and
// -k are present in the array
public static int largestNum(int[] arr)
{
// Stores the array elements
HashSet<int> set = new HashSet<int>();
// Initialize a variable res as
// 0 to store maximum element
// while traversing the array
int res = 0;
// Iterate through array arr
for (int i = 0;
i < arr.Length; i++) {
// Add the current element
// into the set
set.Add(arr[i]);
// Check if the negative of
// this element is also
// present in the set or not
if (set.Contains(-1 * arr[i])) {
res = Math.Max(
res, Math.Abs(arr[i]));
}
}
// Return the resultant element
return res;
}
// Drive Code
static public void Main (){
int[] arr = { 3, 2, -2, 5, -3 };
Console.WriteLine(
largestNum(arr));
}
}
// This code is contributed by unknown2108
Javascript
<script>
// JavaScript program for the above approach
// Function to find the largest
// number k such that both k and
// -k are present in the array
function largestNum(arr)
{
// Stores the array elements
let set = new Set();
// Initialize a variable res as
// 0 to store maximum element
// while traversing the array
let res = 0;
// Iterate through array arr
for (let i = 0;
i < arr.length; i++) {
// Add the current element
// into the set
set.add(arr[i]);
// Check if the negative of
// this element is also
// present in the set or not
if (set.has(-1 * arr[i])) {
res = Math.max(
res, Math.abs(arr[i]));
}
}
// Return the resultant element
return res;
}
// Drive Code
let arr=[3, 2, -2, 5, -3 ];
document.write(largestNum(arr));
// This code is contributed by patel2127
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA