Dada una array de n elementos, la tarea es encontrar el mayor número tal que sea producto de dos elementos de la array dada. Si no existe tal elemento, imprima -1. Los elementos están dentro del rango de 1 a 10^5.
Ejemplos:
Input : arr[] = {10, 3, 5, 30, 35}
Output: 30
Explanation: 30 is the product of 10 and 3.
Input : arr[] = {2, 5, 7, 8}
Output: -1
Explanation: Since, no such element exists.
Input : arr[] = {10, 2, 4, 30, 35}
Output: -1
Input : arr[] = {10, 2, 2, 4, 30, 35}
Output: 4
Input : arr[] = {17, 2, 1, 35, 30}
Output : 35
Un enfoque ingenuo es elegir un elemento y luego verificar cada par de productos si es igual a ese número y actualizar el máximo si el número es máximo, repetir hasta que se atraviese toda la array toma O (n ^ 3) tiempo.
C++
// C++ program to find a pair with product
// in given array.
#include<bits/stdc++.h>
using namespace std;
// Function to find greatest number that us
int findGreatest( int arr[] , int n)
{
int result = -1;
for (int i = 0; i < n ; i++)
for (int j = 0; j < n-1; j++)
for (int k = j+1 ; k < n ; k++)
if (arr[j] * arr[k] == arr[i])
result = max(result, arr[i]);
return result;
}
// Driver code
int main()
{
// Your C++ Code
int arr[] = {30, 10, 9, 3, 35};
int n = sizeof(arr)/sizeof(arr[0]);
cout << findGreatest(arr, n);
return 0;
}
Java
// Java program to find a pair
// with product in given array.
import java.io.*;
class GFG{
static int findGreatest( int []arr , int n)
{
int result = -1;
for (int i = 0; i < n ; i++)
for (int j = 0; j < n-1; j++)
for (int k = j+1 ; k < n ; k++)
if (arr[j] * arr[k] == arr[i])
result = Math.max(result, arr[i]);
return result;
}
// Driver code
static public void main (String[] args)
{
int []arr = {30, 10, 9, 3, 35};
int n = arr.length;
System.out.println(findGreatest(arr, n));
}
}
//This code is contributed by vt_m.
Python 3
# Python 3 program to find a pair # with product in given array. # Function to find greatest number def findGreatest( arr , n): result = -1 for i in range(n): for j in range(n - 1): for k in range(j + 1, n): if (arr[j] * arr[k] == arr[i]): result = max(result, arr[i]) return result # Driver code if __name__ == "__main__": arr = [ 30, 10, 9, 3, 35] n = len(arr) print(findGreatest(arr, n)) # This code is contributed by ita_c
C#
// C# program to find a pair with product
// in given array.
using System;
class GFG{
static int findGreatest( int []arr , int n)
{
int result = -1;
for (int i = 0; i < n ; i++)
for (int j = 0; j < n-1; j++)
for (int k = j+1 ; k < n ; k++)
if (arr[j] * arr[k] == arr[i])
result = Math.Max(result, arr[i]);
return result;
}
// Driver code
static public void Main ()
{
int []arr = {30, 10, 9, 3, 35};
int n = arr.Length;
Console.WriteLine(findGreatest(arr, n));
}
}
//This code is contributed by vt_m.
PHP
<?php
// PHP program to find a pair
// with product in given array.
// Function to find
// greatest number
function findGreatest($arr , $n)
{
$result = -1;
for ($i = 0; $i < $n ; $i++)
for ($j = 0; $j < $n - 1; $j++)
for ($k = $j + 1 ; $k < $n ; $k++)
if ($arr[$j] * $arr[$k] == $arr[$i])
$result = max($result, $arr[$i]);
return $result;
}
// Driver code
$arr = array(30, 10, 9, 3, 35);
$n = count($arr);
echo findGreatest($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find a pair
// with product in given array.
function findGreatest(arr , n)
{
let result = -1;
for (let i = 0; i < n ; i++)
for (let j = 0; j < n-1; j++)
for (let k = j+1 ; k < n ; k++)
if (arr[j] * arr[k] == arr[i])
result = Math.max(result, arr[i]);
return result;
}
// Driver code
let arr = [30, 10, 9, 3, 35];
let n = arr.length;
document.write(findGreatest(arr, n));
// This code is contributed by splevel62.
</script>
Producción :
30
Complejidad del tiempo : O(n 3 )
Espacio Auxiliar: O(1)
Un método eficiente sigue la siguiente implementación: –
- Cree una tabla hash vacía y almacene todos los elementos de la array en ella.
- Ordene la array en orden ascendente.
- Elija elementos uno por uno desde el final de la array.
- Y comprueba si existe un par cuyo producto sea igual a ese número. En esto se puede lograr la eficiencia. La idea es llegar hasta el sqrt de ese número. Si no obtenemos el par hasta sqrt, eso significa que no existe tal par. Usamos la tabla hash para asegurarnos de que podemos encontrar otro elemento del par en el tiempo O(1).
- Repita los pasos 2 a 3 hasta que obtengamos el elemento o toda la array recorrida.
A continuación se muestra la implementación.
C++
// C++ program to find the largest product number
#include <bits/stdc++.h>
using namespace std;
// Function to find greatest number
int findGreatest(int arr[], int n)
{
// Store occurrences of all elements in hash
// array
unordered_map<int, int> m;
for (int i = 0; i < n; i++)
m[arr[i]]++;
// Sort the array and traverse all elements from
// end.
sort(arr, arr + n);
for (int i = n - 1; i > 1; i--) {
// For every element, check if there is another
// element which divides it.
for (int j = 0; j < i && arr[j] <= sqrt(arr[i]);
j++) {
if (arr[i] % arr[j] == 0) {
int result = arr[i] / arr[j];
// Check if the result value exists in array
// or not if yes the return arr[i]
if (result != arr[j] && result!=arr[i] && m[result] > 0)
return arr[i];
// To handle the case like arr[i] = 4 and
// arr[j] = 2
else if (result == arr[j] && m[result] > 1)
return arr[i];
}
}
}
return -1;
}
// Drivers code
int main()
{
int arr[] = { 17, 2, 1, 15, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findGreatest(arr, n);
return 0;
}
Java
// Java program to find the largest product number
import java.util.*;
class GFG
{
// Function to find greatest number
static int findGreatest(int arr[], int n)
{
// Store occurrences of all
// elements in hash array
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < n; i++)
{
if (m.containsKey(arr[i]))
{
m.put(arr[i], m.get(arr[i]) + 1);
}
else
{
m.put(arr[i], m.get(arr[i]));
}
}
// m[arr[i]]++;
// Sort the array and traverse
// all elements from end.
Arrays.sort(arr);
for (int i = n - 1; i > 1; i--)
{
// For every element, check if there is another
// element which divides it.
for (int j = 0; j < i &&
arr[j] <= Math.sqrt(arr[i]); j++)
{
if (arr[i] % arr[j] == 0)
{
int result = arr[i] / arr[j];
// Check if the result value exists in array
// or not if yes the return arr[i]
if (result != arr[j] &&
m.get(result) == null|| m.get(result) > 0)
{
return arr[i];
}
// To handle the case like arr[i] = 4
// and arr[j] = 2
else if (result == arr[j] && m.get(result) > 1)
{
return arr[i];
}
}
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {17, 2, 1, 15, 30};
int n = arr.length;
System.out.println(findGreatest(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Python
# Python3 program to find the largest product number from math import sqrt # Function to find greatest number def findGreatest(arr, n): # Store occurrences of all elements in hash # array m = dict() for i in arr: m[i] = m.get(i, 0) + 1 # Sort the array and traverse all elements from # end. arr=sorted(arr) for i in range(n - 1, 0, -1): # For every element, check if there is another # element which divides it. j = 0 while(j < i and arr[j] <= sqrt(arr[i])): if (arr[i] % arr[j] == 0): result = arr[i]//arr[j] # Check if the result value exists in array # or not if yes the return arr[i] if (result != arr[j] and (result in m.keys() )and m[result] > 0): return arr[i] # To handle the case like arr[i] = 4 and # arr[j] = 2 elif (result == arr[j] and (result in m.keys()) and m[result] > 1): return arr[i] j += 1 return -1 # Drivers code arr= [17, 2, 1, 15, 30] n = len(arr) print(findGreatest(arr, n)) # This code is contributed by mohit kumar
C#
// C# program to find the largest product number
using System;
using System.Collections.Generic;
class GFG
{
// Function to find greatest number
static int findGreatest(int []arr, int n)
{
// Store occurrences of all
// elements in hash array
Dictionary<int,int> m = new Dictionary<int,int> ();
for (int i = 0; i < n; i++)
{
if (m.ContainsKey(arr[i]))
{
var a = m[arr[i]] + 1;
// m.Remove(arr[i]);
m.Add(arr[i], a);
}
else
{
m.Add(arr[i], arr[i]);
}
}
// m[arr[i]]++;
// Sort the array and traverse
// all elements from end.
Array.Sort(arr);
for (int i = n - 1; i > 1; i--)
{
// For every element, check if there is another
// element which divides it.
for (int j = 0; j < i &&
arr[j] <= Math.Sqrt(arr[i]); j++)
{
if (arr[i] % arr[j] == 0)
{
int result = arr[i] / arr[j];
// Check if the result value exists in array
// or not if yes the return arr[i]
if (result != arr[j] &&
m[result] == null|| m[result] > 0)
{
return arr[i];
}
// To handle the case like arr[i] = 4
// and arr[j] = 2
else if (result == arr[j] && m[result] > 1)
{
return arr[i];
}
}
}
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {17, 2, 1, 15, 30};
int n = arr.Length;
Console.WriteLine(findGreatest(arr, n));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the largest product number
// Function to find greatest number
function findGreatest(arr,n)
{
// Store occurrences of all
// elements in hash array
let m = new Map();
for (let i = 0; i < n; i++)
{
if (m.has(arr[i]))
{
m.set(arr[i], m[arr[i]] + 1);
}
else
{
m.set(arr[i], m.get(arr[i]));
}
}
// m[arr[i]]++;
// Sort the array and traverse
// all elements from end.
arr.sort(function(a,b){return a-b;});
for (let i = n - 1; i > 1; i--)
{
// For every element, check if there is another
// element which divides it.
for (let j = 0; j < i &&
arr[j] <= Math.sqrt(arr[i]); j++)
{
if (arr[i] % arr[j] == 0)
{
let result = Math.floor(arr[i] / arr[j]);
// Check if the result value exists in array
// or not if yes the return arr[i]
if (result != arr[j] &&
m[result] == null|| m[result] > 0)
{
return arr[i];
}
// To handle the case like arr[i] = 4
// and arr[j] = 2
else if (result == arr[j] && m[result] > 1)
{
return arr[i];
}
}
}
}
return -1;
}
// Driver code
let arr=[17, 2, 1, 15, 30];
let n = arr.length;
document.write(findGreatest(arr, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción :
30
Complejidad de tiempo: O (nlogn)
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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