No of pairs (a[j] >= a[i]) with k numbers in range (a[i], a[j]) that are divisible by x

0 0 6 minutes read

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.

Output

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.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!