Find index of pair among given pairs with just greater average
Given an array of pairs arr[] of size N where the first value of all the pairs are distinct. For each pair of the given array find the index of another pair which have an average just greater than this one.
Note: The average of two numbers a and b is defined as the floor ( a + b ) / 2.
Examples:
Input: { {2, 3}, {1, 3}, {3, 4} }
Output: { 2, 2, -1}
Explanation: The average all corresponding pair elements are {2, 2, 3}Input: { {3, 5}, {1, 3}, {2, 4} }
Output: { -1, 2, 0 }
Explanation: The average all corresponding pair elements are {4, 2, 3}.
So for {1, 3} though {3, 5} has greater average but
{2, 4} has average just greater than {1, 3} in the given array.
Approach: This problem can be solved using binary search. Follow the steps mentioned below:
- Sort the array of pairs on the basis of average values.
- Apply binary search for each element to find the pair having average value just greater than this one.
- To keep the track of indices, use a hashmap or unordered map as the first values are distinct in all pairs.
Below is the implementation of the above approach:
C++
// C++ program to implement above approach #include <bits/stdc++.h> using namespace std; // Applying custom lower bound // on average values int lbound(vector<pair< int , int > >& arr, int & target) { // Initializing low and high variables int low = 0, high = ( int )arr.size() - 1; // ans keeps the track of desired index int ans = -1; // Applying binary search while (low <= high) { int mid = (low + high) / 2; int avg = (arr[mid].first + arr[mid].second) / 2; if (avg <= target) low = mid + 1; else { high = mid - 1; ans = mid; } } if (ans == -1) return -1; // Return the ans int avg = (arr[ans].first + arr[ans].second) / 2; if (avg > target) return ans; return -1; } // Compare function bool compare(pair< int , int >& a, pair< int , int >& b) { int val1 = (a.first + a.second) / 2; int val2 = (b.first + b.second) / 2; return val1 <= val2; } // Function to find indices of desired pair // for each element of the array of pairs void findPair(vector<pair< int , int > >& arr, int N) { // Declaring an unordered map // to keep the track of // indices since the order // is going to be changed unordered_map< int , int > lookUp; // Iterating over the given vector for ( int i = 0; i < N; i++) { lookUp[arr[i].first] = i; } // Sorting the given vector of pairs // by passing a custom comparator sort(arr.begin(), arr.end(), compare); // Declaring ans vector to store // the final answer vector< int > ans(N); for ( int i = 0; i < N; i++) { // Average value int target = (arr[i].first + arr[i].second) / 2; // Calling lbound() function int ind = lbound(arr, target); // If no such pair exists if (ind == -1) ans[lookUp[arr[i].first]] = -1; // If such a pair exists else ans[lookUp[arr[i].first]] = lookUp[arr[ind].first]; } // Print the final array for ( auto x : ans) cout << x << ' ' ; } // Driver code int main() { // Initializing a vector of pairs vector<pair< int , int > > arr = { { 2, 3 }, { 1, 3 }, { 3, 4 } }; // Size of the vector int N = arr.size(); findPair(arr, N); return 0; } |
Java
import java.util.*; import java.io.*; // Java program for the above approach class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } static ArrayList<pair> arr; static int target; // Applying custom lower bound // on average values static int lbound() { // Initializing low and high variables int low = 0 , high = arr.size() - 1 ; // ans keeps the track of desired index int ans = - 1 ; // Applying binary search while (low <= high) { int mid = (low + high) / 2 ; int a = (arr.get(mid).first + arr.get(mid).second) / 2 ; if (a <= target) low = mid + 1 ; else { high = mid - 1 ; ans = mid; } } if (ans == - 1 ){ return - 1 ; } // Return the ans int avg = (arr.get(ans).first + arr.get(ans).second) / 2 ; if (avg > target){ return ans; } return - 1 ; } // Compare function static class Comp implements Comparator<pair>{ public int compare(pair a, pair b){ return ((a.first + a.second) / 2 )-((b.first + b.second) / 2 ); } } // Function to find indices of desired pair // for each element of the array of pairs static void findPair( int N) { // Declaring an unordered map // to keep the track of // indices since the order // is going to be changed HashMap<Integer, Integer> lookUp = new HashMap<Integer, Integer>(); // Iterating over the given vector for ( int i = 0 ; i < N ; i++) { lookUp.put(arr.get(i).first, i); } // Sorting the given vector of pairs // by passing a custom comparator Collections.sort(arr, new Comp()); // Declaring ans vector to store // the readonly answer ArrayList<Integer> ans = new ArrayList<Integer>(); for ( int i = 0 ; i < N ; i++) { ans.add( 0 ); // Average value target = (arr.get(i).first + arr.get(i).second) / 2 ; // Calling lbound() function int ind = lbound(); // If no such pair exists if (ind == - 1 ) ans.set(lookUp.get(arr.get(i).first), - 1 ); // If such a pair exists else ans.set(lookUp.get(arr.get(i).first), lookUp.get(arr.get(ind).first)); } // Print the readonly array for ( int i = 0 ; i < ans.size() ; i++){ System.out.print(ans.get(i) + " " ); } System.out.println( "" ); } public static void main(String args[]) { // Initializing a vector of pairs arr = new ArrayList<pair>(); arr.add( new pair( 2 , 3 )); arr.add( new pair( 1 , 3 )); arr.add( new pair( 3 , 4 )); // Size of the vector int N = arr.size(); findPair( 3 ); } } // This code is contributed by subhamgoyal2014. |
Python3
# Python3 code for the above approach # Applying custom lower bound # on average values from functools import cmp_to_key def mycmp(a, b): val1 = (a[ 'first' ] + a[ 'second' ]) / / 2 val2 = (b[ 'first' ] + b[ 'second' ]) / / 2 return val1 - val2 def lbound(arr, target): # Initializing low and high variables low,high = 0 , len (arr) - 1 # ans keeps the track of desired index ans = - 1 # Applying binary search while (low < = high): mid = (low + high) / / 2 avg = (arr[mid][ 'first' ] + arr[mid][ 'second' ]) / / 2 if (avg < = target): low = mid + 1 else : high = mid - 1 ans = mid if (ans = = - 1 ): return - 1 # Return the ans avg = (arr[ans][ 'first' ] + arr[ans][ 'second' ]) / / 2 if (avg > target): return ans return - 1 # Function to find indices of desired pair # for each element of the array of pairs def findPair(arr, N): # Declaring an unordered map # to keep the track of # indices since the order # is going to be changed lookUp = [ 0 for i in range ( 1000001 )] # Iterating over the given vector for i in range (N): lookUp[arr[i][ 'first' ]] = i # Sorting the given vector of pairs # by passing a custom comparator arr.sort(key = cmp_to_key(mycmp)) # Declaring ans vector to store # the final answer ans = [ 0 for i in range (N)] for i in range (N): # Average value target = (arr[i][ 'first' ] + arr[i][ 'second' ]) / / 2 # Calling lbound() function ind = lbound(arr, target) # If no such pair exists if (ind = = - 1 ): ans[lookUp[arr[i][ 'first' ]]] = - 1 # If such a pair exists else : ans[lookUp[arr[i][ 'first' ]]] = lookUp[arr[ind][ 'first' ]] # Print the final array for x in ans: print (x ,end = ' ' ) # Driver code # Initializing a list of pairs arr = [{ 'first' : 2 , 'second' : 3 }, { 'first' : 1 , 'second' : 3 }, { 'first' : 3 , 'second' : 4 }] # Size of the vector N = len (arr) findPair(arr, N) # This code is contributed by Shinjanpatra |
C#
// C# program to implement above approach using System; using System.Linq; using System.Collections.Generic; public class GFG { public class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } static List<pair> arr; static int target; // Applying custom lower bound // on average values static int lbound() { // Initializing low and high variables int low = 0, high = arr.Count - 1; // ans keeps the track of desired index int ans = -1; // Applying binary search while (low <= high) { int mid = (low + high) / 2; int a = (arr[mid].first + arr[mid].second) / 2; if (a <= target) low = mid + 1; else { high = mid - 1; ans = mid; } } if (ans == -1) return -1; // Return the ans int avg = (arr[ans].first + arr[ans].second) / 2; if (avg > target) return ans; return -1; } // Compare function // Function to find indices of desired pair // for each element of the array of pairs static void findPair( int N) { // Declaring an unordered map // to keep the track of // indices since the order // is going to be changed Dictionary< int , int > lookUp = new Dictionary< int , int >(); // Iterating over the given vector for ( int i = 0; i < N; i++) { lookUp[arr[i].first] = i; } // Sorting the given vector of pairs // by passing a custom comparator arr.Sort((a, b) => ((a.first + a.second) / 2)-((b.first + b.second) / 2)); // Declaring ans vector to store // the readonly answer List< int > ans = new List< int >(); for ( int i = 0; i < N; i++) { ans.Add(0); // Average value target = (arr[i].first + arr[i].second) / 2; // Calling lbound() function int ind = lbound(); // If no such pair exists if (ind == -1) ans[lookUp[arr[i].first]] = -1; // If such a pair exists else ans[lookUp[arr[i].first]] = lookUp[arr[ind].first]; } // Print the readonly array foreach ( int x in ans) Console.Write(x + " " ); } // Driver code public static void Main(String[] args) { // Initializing a vector of pairs arr = new List<pair>(); arr.Add( new pair(2, 3)); arr.Add( new pair(1, 3)); arr.Add( new pair(3, 4)); // Size of the vector int N = arr.Count; findPair(3); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code for the above approach // Applying custom lower bound // on average values function lbound(arr, target) { // Initializing low and high variables let low = 0, high = arr.length - 1; // ans keeps the track of desired index let ans = -1; // Applying binary search while (low <= high) { let mid = Math.floor((low + high) / 2); let avg = Math.floor((arr[mid].first + arr[mid].second) / 2); if (avg <= target) low = mid + 1; else { high = mid - 1; ans = mid; } } if (ans == -1) return -1; // Return the ans let avg = Math.floor((arr[ans].first + arr[ans].second) / 2); if (avg > target) return ans; return -1; } // Function to find indices of desired pair // for each element of the array of pairs function findPair(arr, N) { // Declaring an unordered map // to keep the track of // indices since the order // is going to be changed let lookUp = new Array(1000001).fill(0); // Iterating over the given vector for (let i = 0; i < N; i++) { lookUp[arr[i].first] = i; } // Sorting the given vector of pairs // by passing a custom comparator arr.sort( function (a, b) { let val1 = Math.floor((a.first + a.second) / 2); let val2 = Math.floor((b.first + b.second) / 2); return val1 - val2; }) // Declaring ans vector to store // the final answer let ans = new Array(N) for (let i = 0; i < N; i++) { // Average value let target = Math.floor((arr[i].first + arr[i].second) / 2); // Calling lbound() function let ind = lbound(arr, target); // If no such pair exists if (ind == -1) ans[lookUp[arr[i].first]] = -1; // If such a pair exists else ans[lookUp[arr[i].first]] = lookUp[arr[ind].first]; } // Print the final array for (let x of ans) document.write(x + ' ' ) } // Driver code // Initializing a vector of pairs let arr = [{ first: 2, second: 3 }, { first: 1, second: 3 }, { first: 3, second: 4 }]; // Size of the vector let N = arr.length; findPair(arr, N); // This code is contributed by Potta Lokesh </script> |
2 2 -1
Time Complexity: O(N * log(N) )
Auxiliary Space: O(N)
Contact Us