Cuente los pares en una array ordenada cuyo producto sea menor que k

Dado un arreglo de enteros ordenados y el número k, la tarea es contar pares en un arreglo cuyo producto sea menor que x.
Ejemplos:
 

Entrada: A = {2, 3, 5, 6}, k = 16 
Salida: 4 
pares que tienen un producto menor que 16: (2, 3), (2, 5), (2, 6), (3, 5)
Entrada: A = {2, 3, 4, 6, 9}, k = 20 
Salida: 6 
pares que tienen un producto menor que 20: (2, 3), (2, 4), (2, 6), (2, 9), (3, 4), (3, 6) 
 

Una solución simple de este problema es ejecutar dos bucles para generar todos los pares uno por uno y verificar si el producto del par actual es menor que x o no.
Una solución eficiente de este problema es tomar el valor inicial y último del índice en la variable l y r. Considere a continuación dos casos:
 

• Caso-I: 
  Consideremos i < j y A[i]*A[j] < k, entonces podemos decir que A[i]*A[j-1] < k como A[j-1] < A[j ] para una array ordenada, del 
  mismo modo A[i]*A[j-2] < k, A[i]*A[j-3] < k, ….., A[i]*A[i+1] < k.
• Caso-II: 
  Consideremos ik, entonces podemos decir que A[i]*A[j+1] > k como A[j+1] > A[j] para una array ordenada, de 
  manera similar A[i]*A[ j+2] > k, A[i]*A[j+3] > k, ….., A[i]*A[n-1] > k.

El problema anterior es similar a contar pares en una array ordenada cuya suma es menor que x , lo único que es diferente es encontrar el producto de pares en lugar de la suma. 
A continuación se muestra el algoritmo para resolver este problema: 
 

1) Initialize two variables l and r to find the candidate 
   elements in the sorted array.
       (a) l = 0
       (b) r = n - 1
2) Initialize : result = 0
2) Loop while l < r.

    // If current left and current
    // right have product smaller than x,
    // the all elements from l+1 to r
    // form a pair with current
    (a) If (arr[l] * arr[r] < x)  
          result = result + (r - l)    
          l++;  
   
    (b) Else
            r--;
       
3) Return result

A continuación se muestra la implementación del algoritmo anterior: 
 

// C++ program to find number of pairs with
// product less than k in a sorted array
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the pairs
int fun(int A[], int n, int k)
{
    // count to keep count of
    // number of pairs with product
    // less than k
    int count = 0;
    int i = 0;
    int j = n - 1;
 
    // Traverse the array
    while (i < j) {
 
        // If product is less than k
        // then count that pair
        // and increment 'i'
        if (A[i] * A[j] < k) {
            count += (j - i);
            i++;
        }
 
        // Else decrement 'j'
        else {
            j--;
        }
    }
 
    // Return count of pairs
    return count;
}
 
// Driver code
int main()
{
 
    int A[] = { 2, 3, 4, 6, 9 };
    int n = sizeof(A) / sizeof(int);
    int k = 20;
    cout << "Number of pairs with product less than "
         << k << " = " << fun(A, n, k) << endl;
 
    return 0;
}

// Java program to find number
// of pairs with product less
// than k in a sorted array
class GFG
{
 
// Function to count the pairs
static int fun(int A[],
               int n, int k)
{
    // count to keep count of
    // number of pairs with
    // product less than k
    int count = 0;
    int i = 0;
    int j = n - 1;
 
    // Traverse the array
    while (i < j)
    {
 
        // If product is less than
        // k then count that pair
        // and increment 'i'
        if (A[i] * A[j] < k)
        {
            count += (j - i);
            i++;
        }
 
        // Else decrement 'j'
        else
        {
            j--;
        }
    }
 
    // Return count of pairs
    return count;
}
 
// Driver code
public static void main(String args[])
{
    int A[] = {2, 3, 4, 6, 9};
    int n = A.length;
    int k = 20;
     
    System.out.println("Number of pairs with " +
                     "product less than 20 = " +
                                  fun(A, n, k));
}
}
 
// This code is contributed
// by Kirti_Mangal

# Python program to find number of pairs with
# product less than k in a sorted array
 
def fun(A, k):
    # count to keep count of number
    # of pairs with product less than k
    count = 0
    n = len(A)
    # Left pointer pointing to leftmost part
    i = 0
     
    # Right pointer pointing to rightmost part
    j = n-1
     
    # While left and right pointer don't meet
    while i < j:
        if A[i]*A[j] < k:
            count += (j-i)
            # Increment the left pointer
            i+= 1
        else:
            # Decrement the right pointer
            j-= 1
    return count
 
# Driver code to test above function
A = [2, 3, 4, 6, 9]
k = 20
print("Number of pairs with product less than ",
k, " = ", fun(A, k))

// C# program to find number
// of pairs with product less
// than k in a sorted array
using System;
 
class GFG
{
 
// Function to count the pairs
static int fun(int []A,
               int n, int k)
{
    // count to keep count of
    // number of pairs with
    // product less than k
    int count = 0;
    int i = 0;
    int j = n - 1;
 
    // Traverse the array
    while (i < j)
    {
 
        // If product is less than
        // k then count that pair
        // and increment 'i'
        if (A[i] * A[j] < k)
        {
            count += (j - i);
            i++;
        }
 
        // Else decrement 'j'
        else
        {
            j--;
        }
    }
 
    // Return count of pairs
    return count;
}
 
// Driver code
public static void Main()
{
    int []A = {2, 3, 4, 6, 9};
    int n = A.Length;
    int k = 20;
     
    Console.WriteLine("Number of pairs with " +
                    "product less than 20 = " +
                                 fun(A, n, k));
}
}
 
// This code is contributed
// by Subhadeep

<?php
// PHP program to find number of
// pairs with product less than k
// in a sorted array
 
// Function to count the pairs
function fun($A, $n, $k)
{
    // count to keep count of
    // number of pairs with product
    // less than k
    $count = 0;
    $i = 0;
    $j = ($n - 1);
 
    // Traverse the array
    while ($i < $j)
    {
 
        // If product is less than k
        // then count that pair
        // and increment 'i'
        if ($A[$i] * $A[$j] < $k)
        {
            $count += ($j - $i);
            $i++;
        }
 
        // Else decrement 'j'
        else
        {
            $j--;
        }
    }
 
    // Return count of pairs
    return $count;
}
 
// Driver code
$A = array( 2, 3, 4, 6, 9 );
$n = sizeof($A);
$k = 20;
echo "Number of pairs with product less than ",
           $k , " = " , fun($A, $n, $k) , "\n";
 
// This code is contributed by ajit
?>

<script>
 
    // Javascript program to find number
    // of pairs with product less
    // than k in a sorted array
     
    // Function to count the pairs
    function fun(A, n, k)
    {
        // count to keep count of
        // number of pairs with
        // product less than k
        let count = 0;
        let i = 0;
        let j = n - 1;
 
        // Traverse the array
        while (i < j)
        {
 
            // If product is less than
            // k then count that pair
            // and increment 'i'
            if (A[i] * A[j] < k)
            {
                count += (j - i);
                i++;
            }
 
            // Else decrement 'j'
            else
            {
                j--;
            }
        }
 
        // Return count of pairs
        return count;
    }
     
    let A = [2, 3, 4, 6, 9];
    let n = A.length;
    let k = 20;
       
    document.write("Number of pairs with " +
                    "product less than 20 = " +
                                 fun(A, n, k));
                                  
</script>

Number of pairs with product less than 20 = 6

Complejidad de tiempo: O(N), donde N es el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.