Given an array arr[] consisting of N integers and an integer X, the task is count the number of pairs (i, j) such that i < j and arr[i] – arr[j] = X * ( j – i ).
Examples:
Input: N = 5, X = 2, arr[] = {1, 5, 5, 7, 11}
Output: 4
Explanation: All the pairs (i, j) such that i < j and arr[j] – arr[i] = X * (j – i) are (0, 2), (0, 3), (1, 4) and (2, 3).
For (0, 2), arr[2] – arr[0] = 5 – 1 = 4 and x * (j – i) = 2 * (2 – 0) = 4, which satisfies the condition arr[j] – arr[i] = x * (j – i), where j = 2, i = 1 and x = 2.
Similarly, the pairs (0, 3), (1, 4) and (2, 3) also satisfy the given condition.Input: N = 6, X = 3, arr[] = {5, 4, 8, 11, 13, 16}
Output: 4
Naive Approach: The simplest approach to solve the problem is to generate all possible pairs from the given array and for each pair, check if the given equation is satisfied or not.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: This problem can be solved using HashMap. Follow the steps below to solve this problem:
- The given condition is arr[j] – arr[i] = X * ( j – i ). This equation can be re-written as arr[j] – arr[i] = x * j – x * i, which can be written as arr[j] – x * j = arr[i] – x * i.
- So now the condition changed to find pairs (i, j) such that i < j and arr[j] – x * j = arr[i] – x * i.
- So all those indexes for which arr[index] – x * index are same, they can be paired. Let us say after going through all iterations the count of arr[index] – x * index is y. So now choose two different indices from y indexes. Which is nothing but yC2, that is equal to (y*(y-1))/2.
- Now, Iterate in the range [0, N-1] using the variable i:
- During each iteration perform arr[index] – x * index. Simultaneously increment the count of arr[index] – x * index.
- Iterate through the map:
- During each iteration perform count = count + (y * (y – 1)) / 2., where y is the second value of map. Which is nothing but count of arr[index] – x * index.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// pairs (i, j) such that i < j and// arr[i] - arr[j] = X*( j - i )void countPairs(int arr[], int n, int x){ // Stores the count of all such // pairs that satisfies the condition. int count = 0; map<int, int> mp; for (int i = 0; i < n; i++) { // Stores count of distinct // values of arr[i] - x * i mp[arr[i] - x * i]++; } // Iterate over the Map for (auto x : mp) { int n = x.second; // Increase count of pairs count += (n * (n - 1)) / 2; } // Print the count of such pairs cout << count;}// Driver Codeint main(){ int n = 6, x = 3; int arr[] = { 5, 4, 8, 11, 13, 16 }; countPairs(arr, n, x); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to count the number of// pairs (i, j) such that i < j and// arr[i] - arr[j] = X*( j - i )static void countPairs(int arr[], int n, int x){ // Stores the count of all such // pairs that satisfies the condition. int count = 0; HashMap<Integer, Integer> mp = new HashMap<>(); for(int i = 0; i < n; i++) { // Stores count of distinct // values of arr[i] - x * i mp.put(arr[i] - x * i, mp.getOrDefault(arr[i] - x * i, 0) + 1); } // Iterate over the Map for(int v : mp.values()) { // Increase count of pairs count += (v * (v - 1)) / 2; } // Print the count of such pairs System.out.println(count);}// Driver Codepublic static void main(String[] args){ int n = 6, x = 3; int arr[] = { 5, 4, 8, 11, 13, 16 }; countPairs(arr, n, x);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to count the number of# pairs (i, j) such that i < j and# arr[i] - arr[j] = X*( j - i )def countPairs(arr, n, x): # Stores the count of all such # pairs that satisfies the condition. count = 0 mp = {} for i in range(n): # Stores count of distinct # values of arr[i] - x * i if ((arr[i] - x * i) in mp): mp[arr[i] - x * i] += 1 else: mp[arr[i] - x * i] = 1 # Iterate over the Map for key, value in mp.items(): n = value # Increase count of pairs count += (n * (n - 1)) // 2 # Print the count of such pairs print(count)# Driver Codeif __name__ == '__main__': n = 6 x = 3 arr = [ 5, 4, 8, 11, 13, 16 ] countPairs(arr, n, x)# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count the number of// pairs (i, j) such that i < j and// arr[i] - arr[j] = X*( j - i )static void countPairs(int[] arr, int n, int x){ // Stores the count of all such // pairs that satisfies the condition. int count = 0; Dictionary<int, int> mp = new Dictionary<int, int>(); for(int i = 0; i < n; i++) { // Stores count of distinct // values of arr[i] - x * i if (!mp.ContainsKey(arr[i] - x * i)) mp[arr[i] - x * i] = 0; mp[arr[i] - x * i] = mp[arr[i] - x * i] + 1; } // Iterate over the Map foreach(KeyValuePair<int, int> v in mp) { // Increase count of pairs count += (v.Value * (v.Value - 1)) / 2; } // Print the count of such pairs Console.WriteLine(count);}// Driver Codepublic static void Main(string[] args){ int n = 6, x = 3; int[] arr = { 5, 4, 8, 11, 13, 16 }; countPairs(arr, n, x);}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program for the above approach// Function to count the number of// pairs (i, j) such that i < j and// arr[i] - arr[j] = X*( j - i )function countPairs(arr, n, x) { // Stores the count of all such // pairs that satisfies the condition. let count = 0; let mp = new Map(); for (let i = 0; i < n; i++) { // Stores count of distinct // values of arr[i] - x * i if (mp.has(arr[i] - x * i)) { mp.set(arr[i] - x * i, mp.get(arr[i] - x * i) + 1) } else { mp.set(arr[i] - x * i, 1) } } // Iterate over the Map for (let x of mp) { let n = x[1]; // Increase count of pairs count += Math.floor((n * (n - 1)) / 2); } // Print the count of such pairs document.write(count);}// Driver Codelet n = 6, x = 3;let arr = [5, 4, 8, 11, 13, 16];countPairs(arr, n, x);// This code is contributed by saurabh_jaiswal.</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
