No of pairs (a[j] >= a[i]) with k numbers in range (a[i], a[j]) that are divisible by x
Given an array and two numbers x and k. Find the number of different ordered pairs of indexes (i, j) such that a[j] >= a[i] and there are exactly k integers num such that num is divisible by x and num is in range a[i]-a[j].
Examples:
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.
A naive approach is to traverse through all pairs possible and count the number of pairs that have k integers in between them which are divisible by x.
Time complexity: O(n^2), as we will be using nested loops for traversing n*n times.
An efficient approach is to sort the array and use binary search to find out the right and left boundaries of numbers(use lower_bound function inbuilt function to do it) which satisfy the condition and which do not. We have to sort the array as it is given every pair should be a[j] >= a[i] irrespective of value of i and j. After sorting we traverse through n elements, and find the number with whose multiplication with x gives a[i]-1, so that we can find k number by adding k to d = a[i]-1/x. So we binary search for the value (d+k)*x to get the multiple with which we can make a pair of a[i] as it will have exactly k integers in between a[i] and a[j]. In this way we get the left boundary for a[j] using binary search in O(log n), and for all other pairs possible with a[i], we need to find out the right-most boundary by searching the number equal to or greater than (d+k+1)*x where we will get k+1 multiples and we get the no of pairs as (right-left) boundary [index-wise].
Implementation:
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. |
Javascript
// Javascript program to calculate the number // pairs satisfying the condition function lower_bound(arr, N, X) { let mid; let low = 0; let high = N; while (low < high) { mid = low + (high - low) / 2; if (X <= arr[mid]) { high = mid; } else { low = mid + 1; } } if (low < N && arr[low] < X) { low++; } return low; } // function to calculate the number of pairs function countPairs(a, n, x, k) { a.sort(); // traverse through all elements let ans = 0; for (let i = 0; i < n; i++) { // current number's divisor let d = (a[i] - 1) / x; // use binary search to find the element // after k multiples of x let it1 = lower_bound(a, n, 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 let it2 = lower_bound( a, n, Math.max((d + k + 1) * x, a[i])); // the difference of index will be the answer ans += it2 - it1; } return ans; } // driver code to check the above function let a = [ 1, 3, 5, 7 ]; let n = 4; let x = 2, k = 1; // function call to get the number of pairs console.log(countPairs(a, n, x, k)); // This code is contributed by garg28harsh. |
3
Time Complexity: O(N*logN), as we are using sort function which will cost N*logN.
Auxiliary Space: O(1), as we are not using any extra space.