Dada una array arr[] de tamaño N, y los números enteros L y R , la tarea es contar el número de pares [arr i , arr j ] tales que i < j y el producto de arr[i] * arr[j] se encuentra en el rango dado [L, R] , es decir, L ≤ arr[i] * arr[j] ≤ R.
Ejemplos:
Entrada: arr[ ] = {4, 1, 2, 5}, L = 4, R = 9
Salida: 3
Explicación: Los pares válidos son {4, 1}, {1, 5} y {4, 2}.Entrada: arr[ ] = { 1, 2, 5, 10, 5 }, L = 2, R = 15
Salida: 6
Explicación: Los pares válidos son {1, 2}, {1, 5}, {1, 10 }, {1, 5}, {2, 5}, {2, 5}.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los pares posibles a partir de la array y, para cada par, verificar si su producto se encuentra en el rango [L, R] o no.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver mediante la técnica de clasificación y búsqueda binaria . Siga los pasos a continuación para resolver este problema:
- Ordene la array arr[].
- Inicialice una variable, digamos ans como 0, para almacenar el número de pares cuyo producto se encuentra en el rango [L, R].
- Iterar sobre el rango [0, N-1] usando una variable i y realizar los siguientes pasos :
- Encuentre el límite superior de un elemento tal que el elemento sea menor que igual a R / arr[i].
- Encuentre el límite inferior de un elemento tal que el elemento sea mayor o igual que L / arr[i].
- Agregar límite superior – límite inferior a ans
- Después de completar los pasos anteriores, imprima ans .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count pairs from an array
// whose product lies in the range [l, r]
void countPairs(int arr[], int l,
int r, int n)
{
// Sort the array arr[]
sort(arr, arr + n);
// Stores the final answer
int ans = 0;
for (int i = 0; i < n; i++) {
// Upper Bound for arr[j] such
// that arr[j] <= r/arr[i]
auto itr1 = upper_bound(
arr + i + 1,
arr + n, r / arr[i])
- arr;
// Lower Bound for arr[j] such
// that arr[j] >= l/arr[i]
auto itr2 = lower_bound(
arr + i + 1, arr + n,
ceil(double(l) / double(arr[i])))
- arr;
ans += itr1 - itr2;
}
// Print the answer
cout << ans << endl;
}
// Driver Code
int main()
{
// Given Input
int arr[] = { 2,2 };
int l = 5, r = 9;
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
countPairs(arr, l, r, n);
return 0;
}
Java
// Java program for above approach
import java.util.Arrays;
class GFG{
// Function to count pairs from an array
// whose product lies in the range [l, r]
public static void countPairs(int[] arr, int l,
int r, int n)
{
// Sort the array arr[]
Arrays.sort(arr);
// Stores the final answer
int ans = 0;
for(int i = 0; i < n; i++)
{
// Upper Bound for arr[j] such
// that arr[j] <= r/arr[i]
int itr1 = upper_bound(arr, 0, arr.length - 1,
l / arr[i]);
// Lower Bound for arr[j] such
// that arr[j] >= l/arr[i]
int itr2 = lower_bound(arr, 0, arr.length - 1,
l / arr[i]);
ans += itr1 - itr2;
}
// Print the answer
System.out.println(ans);
}
public static int lower_bound(int[] arr, int low,
int high, int X)
{
// Base Case
if (low > high)
{
return low;
}
// Find the middle index
int mid = low + (high - low) / 2;
// If arr[mid] is greater than
// or equal to X then search
// in left subarray
if (arr[mid] >= X)
{
return lower_bound(arr, low, mid - 1, X);
}
// If arr[mid] is less than X
// then search in right subarray
return lower_bound(arr, mid + 1, high, X);
}
public static int upper_bound(int[] arr, int low,
int high, int X)
{
// Base Case
if (low > high)
return low;
// Find the middle index
int mid = low + (high - low) / 2;
// If arr[mid] is less than
// or equal to X search in
// right subarray
if (arr[mid] <= X)
{
return upper_bound(arr, mid + 1, high, X);
}
// If arr[mid] is greater than X
// then search in left subarray
return upper_bound(arr, low, mid - 1, X);
}
// Driver Code
public static void main(String args[])
{
// Given Input
int[] arr = { 4, 1, 2, 5 };
int l = 4, r = 9;
int n = arr.length;
// Function Call
countPairs(arr, l, r, n);
}
}
// This code is contributed by gfgking.
Python3
# Python program for above approach # Function to count pairs from an array # whose product lies in the range [l, r] def countPairs(arr, l, r, n): # Sort the array arr[] arr[::-1] # Stores the final answer ans = 0; for i in range(n): # Upper Bound for arr[j] such # that arr[j] <= r/arr[i] itr1 = upper_bound(arr, 0, len(arr) - 1, l // arr[i]) # Lower Bound for arr[j] such # that arr[j] >= l/arr[i] itr2 = lower_bound(arr, 0, len(arr) - 1, l // arr[i]); ans += itr1 - itr2; # Print the answer print(ans); def lower_bound(arr, low, high, X): # Base Case if (low > high): return low; # Find the middle index mid = low + (high - low) // 2; # If arr[mid] is greater than # or equal to X then search # in left subarray if (arr[mid] >= X): return lower_bound(arr, low, mid - 1, X); # If arr[mid] is less than X # then search in right subarray return lower_bound(arr, mid + 1, high, X); def upper_bound(arr, low, high, X): # Base Case if (low > high): return low; # Find the middle index mid = low + (high - low) // 2; # If arr[mid] is less than # or equal to X search in # right subarray if (arr[mid] <= X): return upper_bound(arr, mid + 1, high, X); # If arr[mid] is greater than X # then search in left subarray return upper_bound(arr, low, mid - 1, X); # Driver Code # Given Input arr = [4, 1, 2, 5]; l = 4; r = 9; n = len(arr) # Function Call countPairs(arr, l, r, n); # This code is contributed by _Saurabh_Jaiswal.
C#
// C# program for the above approach
using System;
class GFG{
// Function to count pairs from an array
// whose product lies in the range [l, r]
public static void countPairs(int[] arr, int l,
int r, int n)
{
// Sort the array arr[]
Array.Sort(arr);
// Stores the final answer
int ans = 0;
for(int i = 0; i < n; i++)
{
// Upper Bound for arr[j] such
// that arr[j] <= r/arr[i]
int itr1 = upper_bound(arr, 0, arr.Length - 1,
l / arr[i]);
// Lower Bound for arr[j] such
// that arr[j] >= l/arr[i]
int itr2 = lower_bound(arr, 0, arr.Length - 1,
l / arr[i]);
ans += itr1 - itr2;
}
// Print the answer
Console.WriteLine(ans);
}
public static int lower_bound(int[] arr, int low,
int high, int X)
{
// Base Case
if (low > high)
{
return low;
}
// Find the middle index
int mid = low + (high - low) / 2;
// If arr[mid] is greater than
// or equal to X then search
// in left subarray
if (arr[mid] >= X)
{
return lower_bound(arr, low, mid - 1, X);
}
// If arr[mid] is less than X
// then search in right subarray
return lower_bound(arr, mid + 1, high, X);
}
public static int upper_bound(int[] arr, int low,
int high, int X)
{
// Base Case
if (low > high)
return low;
// Find the middle index
int mid = low + (high - low) / 2;
// If arr[mid] is less than
// or equal to X search in
// right subarray
if (arr[mid] <= X)
{
return upper_bound(arr, mid + 1, high, X);
}
// If arr[mid] is greater than X
// then search in left subarray
return upper_bound(arr, low, mid - 1, X);
}
// Driver code
public static void Main(string[] args)
{
// Given Input
int[] arr = { 4, 1, 2, 5 };
int l = 4, r = 9;
int n = arr.Length;
// Function Call
countPairs(arr, l, r, n);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for above approach
// Function to count pairs from an array
// whose product lies in the range [l, r]
function countPairs(arr, l, r, n)
{
// Sort the array arr[]
arr.sort((a, b) => a - b);
// Stores the final answer
let ans = 0;
for (let i = 0; i < n; i++)
{
// Upper Bound for arr[j] such
// that arr[j] <= r/arr[i]
let itr1 = upper_bound(arr, 0, arr.length - 1, Math.floor(l / arr[i]));
// Lower Bound for arr[j] such
// that arr[j] >= l/arr[i]
let itr2 = lower_bound(arr, 0, arr.length - 1, Math.floor(l / arr[i]));
ans += itr1 - itr2;
}
// Print the answer
document.write(ans + "<br>");
}
function lower_bound(arr, low, high, X) {
// Base Case
if (low > high) {
return low;
}
// Find the middle index
let mid = Math.floor(low + (high - low) / 2);
// If arr[mid] is greater than
// or equal to X then search
// in left subarray
if (arr[mid] >= X) {
return lower_bound(arr, low, mid - 1, X);
}
// If arr[mid] is less than X
// then search in right subarray
return lower_bound(arr, mid + 1, high, X);
}
function upper_bound(arr, low, high, X) {
// Base Case
if (low > high)
return low;
// Find the middle index
let mid = Math.floor(low + (high - low) / 2);
// If arr[mid] is less than
// or equal to X search in
// right subarray
if (arr[mid] <= X) {
return upper_bound(arr, mid + 1, high, X);
}
// If arr[mid] is greater than X
// then search in left subarray
return upper_bound(arr, low, mid - 1, X);
}
// Driver Code
// Given Input
let arr = [4, 1, 2, 5];
let l = 4, r = 9;
let n = arr.length
// Function Call
countPairs(arr, l, r, n);
// This code is contributed by gfgking.
</script>
Producción:
3
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dinijain99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA