An approach using Hashing
As per the valid pair is concerned the value of j – i != arr[j] – arr[i], This can also be written as j – arr[j] != i – arr[i].
We’ll use map to keep the count of element that has value (i – arr[i]) occurred till ith index. If we are at ith index then the valid pair for ith element would be just (Total number of pairs till ith index – count of element that has value (i – arr[i]) till ith index).
Follow the steps below to implement the above idea:
- Initialize a map for storing the value of (i – arr[i])
- Initialize a variable result for storing the count of all valid pairs
- Iterate over the given array
- Store the count of all the previous element that has value (i – arr[i]) into a variable count, as this will act as all invalid pair with the element at the ith index.
- Add all valid pairs by removing the invalid pairs into the result (i.e, result += i – count).
- Increment the count of (i – arr[i]) into map for every ith index.
- Return the result.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the number of valid pairs long long validPairs(vector< int >& arr) { // Initialize a map for storing the // value of (i - arr[i]) unordered_map< int , int > unmap; // Initialize a variable result for // storing the count of all valid // pairs long long result = 0; // Iterate over the given array for ( int i = 0; i < arr.size(); i++) { // Calculate number of time value // (i - arr[i]) has occurred till // ith index All the previous // element that has value // (i - arr[i]) will be act as // invalid Pair with element at // ith index. long long count = unmap[i - arr[i]]; // Add all valid pair by remove // the invalid pairs result += i - count; // Store the value of (i - arr[i]) // into map unmap[i - arr[i]]++; } // Return the result. return result; } // Driver's code int main() { vector< int > arr = { 4, 1, 3, 3 }; // Function Call cout << validPairs(arr); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Function to find the number of valid pairs static long validPairs( int [] arr) { // Initialize a map for storing the // value of (i - arr[i]) HashMap<Integer, Integer> unmap = new HashMap<>(); // Initialize a variable result for // storing the count of all valid // pairs long result = 0 ; // Iterate over the given array for ( int i = 0 ; i < arr.length; i++) { long count = 0 ; // Calculate number of time value // (i - arr[i]) has occurred till // ith index All the previous // element that has value // (i - arr[i]) will be act as // invalid Pair with element at // ith index. if (unmap.containsKey(i - arr[i])) { count = unmap.get(i - arr[i]); } // Add all valid pair by remove // the invalid pairs result += i - count; // Store the value of (i - arr[i]) // into map if (unmap.containsKey(i - arr[i])) { unmap.put(i - arr[i], unmap.get(i - arr[i]) + 1 ); } else { unmap.put(i - arr[i], 1 ); } } // Return the result. return result; } public static void main(String[] args) { int [] arr = { 4 , 1 , 3 , 3 }; // Function call System.out.print(validPairs(arr)); } } // This code is contributed by lokesh |
Python3
# Python code to implement the approach # Function to find the number of valid pairs def validPairs(arr): # Initialize a map for storing the # value of (i - arr[i]) unmap = {} # Initialize a variable result for # storing the count of all valid # pairs result = 0 # Iterate over the given array for i in range ( len (arr)): # Calculate number of time value # (i - arr[i]) has occurred till # ith index All the previous # element that has value # (i - arr[i]) will be act as # invalid Pair with element at # ith index. count = 0 if (i - arr[i] in unmap): count = unmap[i - arr[i]] # Add all valid pair by remove # the invalid pairs result = result + i - count # Store the value of (i - arr[i]) # into map if (i - arr[i] in unmap): unmap[i - arr[i]] = unmap[i - arr[i]] + 1 else : unmap[i - arr[i]] = 1 # Return the result. return result # Driver code arr = [ 4 , 1 , 3 , 3 ] # Function Call print (validPairs(arr)) # This code is contributed Pushpesh Raj. |
C#
// C# code to implement the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the number of valid pairs static long validPairs( int [] arr) { // Initialize a map for storing the // value of (i - arr[i]) Dictionary< int , int > unmap = new Dictionary< int , int >(); // Initialize a variable result for // storing the count of all valid // pairs long result = 0; // Iterate over the given array for ( int i = 0; i < arr.Length; i++) { long count = 0; // Calculate number of time value // (i - arr[i]) has occurred till // ith index All the previous // element that has value // (i - arr[i]) will be act as // invalid Pair with element at // ith index. if (unmap.ContainsKey(i - arr[i])) { count = unmap[(i - arr[i])]; } // Add all valid pair by remove // the invalid pairs result += i - count; // Store the value of (i - arr[i]) // into map if (unmap.ContainsKey(i - arr[i])) { unmap[i - arr[i]]++; } else { unmap[i - arr[i]] = 1; } } // Return the result. return result; } // Driver function public static void Main( string [] args) { int [] arr = { 4, 1, 3, 3 }; // Function call Console.WriteLine(validPairs(arr)); } } // This code is contributed by sanjoy_62. |
Javascript
// JavaScript code for the above approach // Function to find the number of valid pairs function validPairs(arr) { // Initialize a map for storing the // value of (i - arr[i]) let unmap = new Map(); // Initialize a variable result for // storing the count of all valid // pairs let result = 0; // Iterate over the given array for (let i = 0; i < arr.length; i++) { // Calculate number of time value // (i - arr[i]) has occurred till // ith index All the previous // element that has value // (i - arr[i]) will be act as // invalid Pair with element at // ith index. let count = 0; if (unmap.has(i - arr[i])) count = unmap.get(i - arr[i]); // Add all valid pair by remove // the invalid pairs result += i - count; // Store the value of (i - arr[i]) // into map if (unmap.has(i - arr[i])) unmap.set(i - arr[i], unmap.get(i - arr[i]) + 1); else unmap.set(i - arr[i], 1); } // Return the result. return result; } // Driver's code let arr = [ 4, 1, 3, 3 ]; // Function Call console.log(validPairs(arr)); // This code is contributed by Potta Lokesh |
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Count pairs such that difference between them and indices are different
Given an array arr[] of size N, the task is to count all pair of indices (i, j) such that i < j and j – i != arr[j] – arr[i].
Examples:
Input: arr[] = {4, 1, 3, 3}
Output: 5
Explanation:
The pair (0, 1) is a valid pair since 1 – 0 != 1 – 4.
The pair (0, 2) is a valid pair since 2 – 0 != 3 – 4, 2 != -1.
The pair (0, 3) is a valid pair since 3 – 0 != 3 – 4, 3 != -1.
The pair (1, 2) is a valid pair since 2 – 1 != 3 – 1, 1 != 2.
The pair (2, 3) is a valid pair since 3 – 2 != 3 – 3, 1 != 0.
There are a total of 5 valid pairs, so we return 5.Input: arr = {1, 2, 3, 4, 5}
Output: 0
Explanation: There are no valid pairs.