Dada una array y dos números x y k. Encuentra el número de diferentes pares ordenados de índices (i, j) tales que a[j] >= a[i] y hay exactamente k enteros num tales que num es divisible por x y num está en el rango a[i]- una[j].
Ejemplos:
Input : arr[] = {1, 3, 5, 7}
x = 2, k = 1
Output : 3
Explanation: The pairs (1, 3), (3, 5) and (5, 7)
have k (which is 1) integers i.e., 2, 4, 6
respectively for every pair in between them.
Input : arr[] = {5, 3, 1, 7}
x = 2, k = 0
Output : 4
Explanation: The pairs with indexes (1, 1), (2, 2),
(3, 3), (4, 4) have k = 0 integers that are
divisible by 2 in between them.
Un enfoque ingenuo es atravesar todos los pares posibles y contar el número de pares que tienen k enteros entre ellos que son divisibles por x.
Complejidad de tiempo: O(n^2) , ya que usaremos bucles anidados para atravesar n*n veces.
Un enfoque eficiente es ordenar la array y usar la búsqueda binaria para encontrar los límites derecho e izquierdo de los números (use la función lower_boundfunción incorporada para hacerlo) que satisfacen la condición y cuáles no. Tenemos que ordenar la array tal como se da, cada par debe ser a[j] >= a[i] independientemente del valor de i y j. Después de clasificar, recorremos n elementos y encontramos el número cuya multiplicación con x da a[i]-1, de modo que podemos encontrar k número sumando k a d = a[i]-1/x. Así que buscamos binariamente el valor (d+k)*x para obtener el múltiplo con el que podemos hacer un par de a[i], ya que tendrá exactamente k enteros entre a[i] y a[j]. De esta manera, obtenemos el límite izquierdo para a[j] usando la búsqueda binaria en O(log n), y para todos los demás pares posibles con a[i], necesitamos encontrar el límite más a la derecha buscando el número igual a o mayor que (d+k+1)*x donde obtendremos k+1 múltiplos y obtenemos el número de pares como límite (derecha-izquierda) [índice sabio].
Implementación:
C++
// C++ program to calculate the number
// pairs satisfying the condition
#include <bits/stdc++.h>
using namespace std;
// function to calculate the number of pairs
int countPairs(int a[], int n, int x, int k)
{
sort(a, a + n);
// traverse through all elements
int ans = 0;
for (int i = 0; i < n; i++) {
// current number's divisor
int d = (a[i] - 1) / x;
// use binary search to find the element
// after k multiples of x
int it1 = lower_bound(a, a + n,
max((d + k) * x, a[i])) - a;
// use binary search to find the element
// after k+1 multiples of x so that we get
// the answer by subtracting
int it2 = lower_bound(a, a + n,
max((d + k + 1) * x, a[i])) - a;
// the difference of index will be the answer
ans += it2 - it1;
}
return ans;
}
// driver code to check the above function
int main()
{
int a[] = { 1, 3, 5, 7 };
int n = sizeof(a) / sizeof(a[0]);
int x = 2, k = 1;
// function call to get the number of pairs
cout << countPairs(a, n, x, k);
return 0;
}
Java
// Java program to calculate the number
// pairs satisfying the condition
import java.util.*;
class GFG
{
// function to calculate the number of pairs
static int countPairs(int a[], int n, int x, int k)
{
Arrays.sort(a);
// traverse through all elements
int ans = 0;
for (int i = 0; i < n; i++)
{
// current number's divisor
int d = (a[i] - 1) / x;
// use binary search to find the element
// after k multiples of x
int it1 = Arrays.binarySearch(a,
Math.max((d + k) * x, a[i]));
// use binary search to find the element
// after k+1 multiples of x so that we get
// the answer by subtracting
int it2 = Arrays.binarySearch(a,
Math.max((d + k + 1) * x, a[i])) ;
// the difference of index will be the answer
ans += it1 - it2;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int []a = { 1, 3, 5, 7 };
int n = a.length;
int x = 2, k = 1;
// function call to get the number of pairs
System.out.println(countPairs(a, n, x, k));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to calculate the number # pairs satisfying the condition import bisect # function to calculate the number of pairs def countPairs(a, n, x, k): a.sort() # traverse through all elements ans = 0 for i in range(n): # current number's divisor d = (a[i] - 1) // x # use binary search to find the element # after k multiples of x it1 = bisect.bisect_left(a, max((d + k) * x, a[i])) # use binary search to find the element # after k+1 multiples of x so that we get # the answer by subtracting it2 = bisect.bisect_left(a, max((d + k + 1) * x, a[i])) # the difference of index will be the answer ans += it2 - it1 return ans # Driver code if __name__ == "__main__": a = [1, 3, 5, 7] n = len(a) x = 2 k = 1 # function call to get the number of pairs print(countPairs(a, n, x, k)) # This code is contributed by # sanjeev2552
C#
// C# program to calculate the number
// pairs satisfying the condition
using System;
class GFG{
// Function to calculate the number of pairs
static int countPairs(int[] a, int n,
int x, int k)
{
Array.Sort(a);
// Traverse through all elements
int ans = 0;
for(int i = 0; i < n; i++)
{
// Current number's divisor
int d = (a[i] - 1) / x;
// Use binary search to find the element
// after k multiples of x
int a1 = Math.Max((d + k) * x, a[i]);
int it1 = Array.BinarySearch(a, a1);
// Use binary search to find the element
// after k+1 multiples of x so that we get
// the answer by subtracting
int a2 = Math.Max((d + k + 1) * x, a[i]);
int it2 = Array.BinarySearch(a, a2);
// The difference of index will
// be the answer
ans += Math.Abs(it2 - it1);
}
return ans;
}
// Driver Code
static void Main()
{
int[] a = { 1, 3, 5, 7 };
int n = a.Length;
int x = 2, k = 1;
// Function call to get the number of pairs
Console.Write(countPairs(a, n, x, k));
}
}
// This code is contributed by SoumikMondal.
3
Complejidad de tiempo: O(N*logN) , ya que estamos usando la función de clasificación que costará N*logN.
Espacio auxiliar: O(1) , ya que no estamos utilizando ningún espacio adicional.