Maximum number of Valid Pairs satisfying conditions k*(j – i) != (arr[j] – arr[i])/k
Given an array arr[] of size N and an integer k, the task is to find the maximum number of valid pair of indices (i, j) such that i < j and k*(j – i) != (arr[j] – arr[i])/k.
Example:
Input: arr[] = {4, 1, 5, 3}, k = 2
Output: 5
Explanation: All possible pair is valid except {arr[1] , arr[2]}, because given condition doesn’t meet : 2(2 – 1) == (5 – 1) / 2.Input: arr[] = {1, 2, 3, 4, 5}, k = 1
Output: 0
Explanation: There are no valid pairs.
Approach:
- The condition for a valid pair is when k*(j – i) != (arr[j] – arr[i])/k
- This condition can also be expressed as (j*k2 – arr[j]) !=(i*k2 – arr[i]).
- To find valid pairs, we’ll use a map to keep track of the count of elements with the value (i*k2 – arr[i]) up to the i th index.
- For the i th element, the number of valid pairs is calculated as
Total pairs up to i th index – count of elements with value (i*k2 – arr[i]) up to i th index.
Steps to solve this problem:
- Create a map for storing the value of (ik2 – arr[i])
- Create a variable result for storing the count of all valid pairs
- Iterate over the given array
- Store the count of all the previous elements with value (i*k2 – arr[i]) into a variable count, as this will act as all invalid pairs with the element at the i th index.
- Add all valid pairs by removing the invalid pairs into the result i.e. ( result += i – count).
- Increment the count of (ik2 – arr[i]) into the 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, int k) { // Initilize a map for storing the // value of (ik^2 - arr[i]) unordered_map< int , int > unmap; // Initilize 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 // (ik^2 - arr[i]) has occured till // ith index All the previous // element that has value // (ik^2 - arr[i]) will be act as // invalid Pair with element at // ith index. long long count = unmap[i * k * k - arr[i]]; // Add all valid pair by remove // the invalid pairs result += i - count; // Store the value of (ik^2 - arr[i]) // into map unmap[i * k * k - arr[i]]++; } // Return the result. return result; } // Driver's code int main() { vector< int > arr = { 4, 1, 5, 3 }; int k = 2; // Function Call cout << validPairs(arr, k); return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { // Function to find the number of valid pairs public static long validPairs( int [] arr, int k) { // Initialize a map for storing the value of (i*k^2 // - arr[i]) Map<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++) { // Calculate the number of times value (i*k^2 - // arr[i]) has occurred till the ith index. All // the previous elements that have the value // (i*k^2 - arr[i]) will act as invalid pairs // with the element at the ith index. long count = unmap.getOrDefault(i * k * k - arr[i], 0 ); // Add all valid pairs by removing the invalid // pairs result += i - count; // Store the value of (i*k^2 - arr[i]) in the // map unmap.put( i * k * k - arr[i], unmap.getOrDefault(i * k * k - arr[i], 0 ) + 1 ); } // Return the result return result; } // Driver's code public static void main(String[] args) { int [] arr = { 4 , 1 , 5 , 3 }; int k = 2 ; // Function Call System.out.println(validPairs(arr, k)); } } |
Python3
# Python Implementation def validPairs(arr, k): # Initialize a dictionary for storing the value of (i*k^2 - 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 the number of times value (i*k^2 - arr[i]) has occurred till the ith index # All the previous elements that have value (i*k^2 - arr[i]) will be considered as invalid pairs with the element at the ith index count = unmap.get(i * k * k - arr[i], 0 ) # Add all valid pairs by removing the invalid pairs result + = i - count # Store the value of (i*k^2 - arr[i]) into the dictionary unmap[i * k * k - arr[i]] = unmap.get(i * k * k - arr[i], 0 ) + 1 # Return the result return result # Driver's code arr = [ 4 , 1 , 5 , 3 ] k = 2 # Function call print (validPairs(arr, k)) # This code is contributed by Tapesh(tapeshdua420) |
C#
using System; using System.Collections.Generic; class GFG { // Function to find the number of the valid pairs static long ValidPairs(List< int > arr, int k) { // Initialize a dictionary for storing // value of (i * k^2 - arr[i]) Dictionary< long , long > map = new Dictionary< long , long >(); long result = 0; // Iterate over the given array for ( int i = 0; i < arr.Count; i++) { // Calculate the number of the times the value long count = map.GetValueOrDefault(i * k * k - arr[i], 0); result += i - count; // Store the value of (i * k^2 - arr[i]) into // dictionary if (map.ContainsKey(i * k * k - arr[i])) { map[i * k * k - arr[i]]++; } else { map.Add(i * k * k - arr[i], 1); } } // Return the result return result; } // Driver's code static void Main( string [] args) { List< int > arr = new List< int > { 4, 1, 5, 3 }; int k = 2; Console.WriteLine(ValidPairs(arr, k)); } } |
Javascript
// Function to find the number of valid pairs function validPairs(arr, k) { // Initialize a map for storing the // value of (ik^2 - arr[i]) const 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 the number of times value // (ik^2 - arr[i]) has occurred till // the ith index. All the previous // elements that have the value // (ik^2 - arr[i]) will be treated as // invalid pairs with the element at // the ith index. const count = unmap.get(i * k * k - arr[i]) || 0; // Add all valid pairs by removing // the invalid pairs result += i - count; // Store the value of (ik^2 - arr[i]) // into the map unmap.set(i * k * k - arr[i], (unmap.get(i * k * k - arr[i]) || 0) + 1); } // Return the result return result; } // Driver's code function main() { const arr = [4, 1, 5, 3]; const k = 2; // Function Call console.log(validPairs(arr, k)); } // Call the main function main(); |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us