Dada una array arr[] de N enteros, donde N > 2 , la tarea es encontrar el segundo par de productos más grande de la array dada.
Ejemplos:
Entrada: arr[] = {10, 20, 12, 40, 50}
Salida: 20 50
Explicación:
Un par de elementos de array = [(10, 20), (10, 12), (10, 40), (10 , 50), (20, 12), (20, 40), (20, 50), (12, 40), (12, 50), (40, 50)]
Si el producto de cada par obtendrá el mayor par como (40, 50) y segundo par más grande (20, 50)Entrada: arr[] = {5, 2, 67, 45, 160, 78}
Salida: 67 160
Enfoque ingenuo: el enfoque ingenuo es generar todos los pares posibles a partir de la array dada e insertar el producto con el par en el conjunto de pares. Después de insertar todos los productos pares en el conjunto, imprima el penúltimo producto del conjunto. A continuación se muestran los pasos:
- Haz un conjunto de pares y sus productos con la array dada.
- Inserta todos los pares en el vector de pares.
- Si el tamaño del vector es 1, imprima este par; de lo contrario, imprima el par en (tamaño total del vector – 2) posición del vector.
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 second largest
// product of pairs
void secondLargerstPair(int arr[], int N)
{
// If size of array is less than 3
// then second largest product pair
// does not exits.
if (N < 3)
return;
// Declaring set of pairs which
// contains possible pairs of array
// and their products
set<pair<int, pair<int, int> > > s;
// Declaring vector of pairs
vector<pair<int, int> > v;
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
// Inserting a set
s.insert(make_pair(arr[i] * arr[j],
make_pair(arr[i],
arr[j])));
}
}
// Traverse set of pairs
for (auto i : s) {
// Inserting values in vector
// of pairs
v.push_back(
make_pair((i.second).first,
(i.second).second));
}
int vsize = v.size();
// Printing the result
cout << v[vsize - 2].first << " "
<< v[vsize - 2].second << endl;
}
// Driver Code
int main()
{
// Given Array
int arr[] = { 5, 2, 67, 45, 160, 78 };
// Size of Array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
secondLargerstPair(arr, N);
return 0;
}
Producción:
67 160
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Mejor solución: una mejor solución es atravesar todos los pares de la array y, mientras se atraviesa, almacenar los pares de productos más grande y el segundo más grande. Después del recorrido, imprima los pares con los segundos pares más grandes almacenados.
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 second largest
// product pair in arr[0..n-1]
void maxProduct(int arr[], int N)
{
// No pair exits
if (N < 3) {
return;
}
// Initialize max product pair
int a = arr[0], b = arr[1];
int c = 0, d = 0;
// Traverse through every possible pair
// and keep track of largest product
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++) {
// If pair is largest
if (arr[i] * arr[j] > a * b) {
// Second largest
c = a, d = b;
a = arr[i], b = arr[j];
}
// If pair does not largest but
// larger than second largest
if (arr[i] * arr[j] < a * b
&& arr[i] * arr[j] > c * d)
c = arr[i], d = arr[j];
}
// Print the pairs
cout << c << " " << d;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 5, 2, 67, 45, 160, 78 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
maxProduct(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find second largest
// product pair in arr[0..n-1]
static void maxProduct(int arr[], int N)
{
// No pair exits
if (N < 3)
{
return;
}
// Initialize max product pair
int a = arr[0], b = arr[1];
int c = 0, d = 0;
// Traverse through every possible pair
// and keep track of largest product
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N-1; j++)
{
// If pair is largest
if (arr[i] * arr[j] > a * b)
{
// Second largest
c = a;
d = b;
a = arr[i];
b = arr[j];
}
// If pair does not largest but
// larger than second largest
if (arr[i] * arr[j] < a * b &&
arr[i] * arr[j] > c * d)
c = arr[i];
d = arr[j];
}
// Print the pairs
System.out.println(c + " " + d);
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 5, 2, 67, 45, 160, 78 };
int N = arr.length;
// Function Call
maxProduct(arr, N);
}
}
// This code is contributed by Ritik Bansal
Python3
# Python3 program for the above approach # Function to find second largest # product pair in arr[0..n-1] def maxProduct(arr, N): # No pair exits if (N < 3): return; # Initialize max product pair a = arr[0]; b = arr[1]; c = 0; d = 0; # Traverse through every possible pair # and keep track of largest product for i in range(0, N, 1): for j in range(i + 1, N - 1, 1): # If pair is largest if (arr[i] * arr[j] > a * b): # Second largest c = a; d = b; a = arr[i]; b = arr[j]; # If pair does not largest but # larger than second largest if (arr[i] * arr[j] < a * b and arr[i] * arr[j] > c * d): c = arr[i]; d = arr[j]; # Print the pairs print(c, " ", d); # Driver Code if __name__ == '__main__': # Given array arr = [ 5, 2, 67, 45, 160, 78]; N = len(arr); # Function call maxProduct(arr, N); # This code is contributed by Amit Katiyar
C#
// C# program for the above approach
using System;
class GFG{
// Function to find second largest
// product pair in arr[0..n-1]
static void maxProduct(int []arr, int N)
{
// No pair exits
if (N < 3)
{
return;
}
// Initialize max product pair
int a = arr[0], b = arr[1];
int c = 0, d = 0;
// Traverse through every possible pair
// and keep track of largest product
for(int i = 0; i < N; i++)
for(int j = i + 1; j < N - 1; j++)
{
// If pair is largest
if (arr[i] * arr[j] > a * b)
{
// Second largest
c = a;
d = b;
a = arr[i];
b = arr[j];
}
// If pair does not largest but
// larger than second largest
if (arr[i] * arr[j] < a * b &&
arr[i] * arr[j] > c * d)
c = arr[i];
d = arr[j];
}
// Print the pairs
Console.WriteLine(c + " " + d);
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 5, 2, 67, 45, 160, 78 };
int N = arr.Length;
// Function call
maxProduct(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to find second largest
// product pair in arr[0..n-1]
function maxProduct(arr, N)
{
// No pair exits
if (N < 3) {
return;
}
// Initialize max product pair
let a = arr[0], b = arr[1];
let c = 0, d = 0;
// Traverse through every possible pair
// and keep track of largest product
for (let i = 0; i < N; i++)
for (let j = i + 1; j < N; j++) {
// If pair is largest
if (arr[i] * arr[j] > a * b) {
// Second largest
c = a, d = b;
a = arr[i], b = arr[j];
}
// If pair does not largest but
// larger than second largest
if (arr[i] * arr[j] < a * b
&& arr[i] * arr[j] > c * d)
c = arr[i], d = arr[j];
}
// Print the pairs
document.write(c + " " + d);
}
// Driver Code
// Given array
let arr = [ 5, 2, 67, 45, 160, 78 ];
let N = arr.length;
// Function Call
maxProduct(arr, N);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
67 160
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente:
- Ordenar la array.
- Encuentre el primer y tercer elemento más pequeño para manejar números negativos.
- Encuentre el primer y tercer elemento más grande para manejar números positivos.
- Compara el producto del par más pequeño y el par más grande.
- Devuelve el más grande de ellos.
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 second largest
// product pair in arr[0..n-1]
void maxProduct(int arr[], int N)
{
// No pair exits
if (N < 3) {
return;
}
// Sort the array
sort(arr, arr + N);
// Initialize smallest element
// of the array
int smallest1 = arr[0];
int smallest3 = arr[2];
// Initialize largest element
// of the array
int largest1 = arr[N - 1];
int largest3 = arr[N - 3];
// Print second largest product pair
if (smallest1 * smallest3
>= largest1 * largest3) {
cout << smallest1 << " " << smallest3;
}
else {
cout << largest1 << " " << largest3;
}
}
// Driver Code
int main()
{
// Given array
int arr[] = { 5, 2, 67, 45, 160, 78 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
maxProduct(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find second largest
// product pair in arr[0..n-1]
static void maxProduct(int arr[], int N)
{
// No pair exits
if (N < 3)
{
return;
}
// Sort the array
Arrays.sort(arr);
// Initialize smallest element
// of the array
int smallest1 = arr[0];
int smallest3 = arr[2];
// Initialize largest element
// of the array
int largest1 = arr[N - 1];
int largest3 = arr[N - 3];
// Print second largest product pair
if (smallest1 * smallest3 >=
largest1 * largest3)
{
System.out.print(smallest1 + " " +
smallest3);
}
else
{
System.out.print(largest1 + " " +
largest3);
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 5, 2, 67, 45, 160, 78 };
int N = arr.length;
// Function Call
maxProduct(arr, N);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to find second largest # product pair in arr[0..n-1] def maxProduct(arr, N): # No pair exits if (N < 3): return; # Sort the array arr.sort(); # Initialize smallest element # of the array smallest1 = arr[0]; smallest3 = arr[2]; # Initialize largest element # of the array largest1 = arr[N - 1]; largest3 = arr[N - 3]; # Print second largest product pair if (smallest1 * smallest3 >= largest1 * largest3): print(smallest1 , " " , smallest3); else: print(largest1 , " " , largest3); # Driver Code if __name__ == '__main__': # Given array arr = [5, 2, 67, 45, 160, 78]; N = len(arr); # Function Call maxProduct(arr, N); # This code is contributed by sapnasingh4991
C#
// C# program for the above approach
using System;
class GFG{
// Function to find second largest
// product pair in arr[0..n-1]
static void maxProduct(int []arr, int N)
{
// No pair exits
if (N < 3)
{
return;
}
// Sort the array
Array.Sort(arr);
// Initialize smallest element
// of the array
int smallest1 = arr[0];
int smallest3 = arr[2];
// Initialize largest element
// of the array
int largest1 = arr[N - 1];
int largest3 = arr[N - 3];
// Print second largest product pair
if (smallest1 * smallest3 >=
largest1 * largest3)
{
Console.Write(smallest1 + " " +
smallest3);
}
else
{
Console.Write(largest1 + " " +
largest3);
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 5, 2, 67, 45, 160, 78 };
int N = arr.Length;
// Function Call
maxProduct(arr, N);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program for the above approach
// Function to find second largest
// product pair in arr[0..n-1]
function maxProduct(arr, N)
{
// No pair exits
if (N < 3)
{
return;
}
// Sort the array
arr.sort((a, b) => a - b)
// Initialize smallest element
// of the array
let smallest1 = arr[0];
let smallest3 = arr[2];
// Initialize largest element
// of the array
let largest1 = arr[N - 1];
let largest3 = arr[N - 3];
// Print second largest product pair
if (smallest1 * smallest3 >=
largest1 * largest3)
{
document.write(smallest1 + " " +
smallest3);
}
else
{
document.write(largest1 + " " +
largest3);
}
}
// Driver Code
// Given array
let arr = [ 5, 2, 67, 45, 160, 78 ];
let N = arr.length;
// Function Call
maxProduct(arr, N);
</script>
Producción:
160 67
Complejidad de Tiempo: O(N*log N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por rohitravikantrane y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA