Number of indices pair such that element pair sum from first Array is greater than second Array
Given two integer arrays A[] and B[] of equal sizes, the task is to find the number of pairs of indices {i, j} in the arrays such that A[i] + A[j] > B[i] + B[j] and i < j.
Examples:
Input: A[] = {4, 8, 2, 6, 2}, B[] = {4, 5, 4, 1, 3}
Output: 7
Explanation:
There are a total of 7 pairs of indices {i, j} in the array following the condition. They are:
{0, 1}: A[0] + A[1] > B[0] + B[1]
{0, 3}: A[0] + A[3] > B[0] + B[3]
{1, 2}: A[1] + A[2] > B[1] + B[2]
{1, 3}: A[1] + A[3] > B[1] + B[3]
{1, 4}: A[1] + A[4] > B[1] + B[4]
{2, 3}: A[2] + A[3] > B[2] + B[3]
{3, 4}: A[3] + A[4] > B[3] + B[4]
Input: A[] = {1, 3, 2, 4}, B[] = {1, 3, 2, 4}
Output: 0
Explanation:
No such possible pairs of {i, j} can be found that satisfies the given condition
Naive Approach: The naive approach is to consider all the possible pairs of {i, j} in the given arrays and check if A[i] + A[j] > B[i] + B[j]. This can be done by using the concept of nested loops.
Time Complexity: O(N2)
Implementation:-
C++
// C++ program to find the number of indices pair // such that pair sum from first Array // is greater than second Array #include <bits/stdc++.h> using namespace std; // Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] int getPairs(vector< int > A, vector< int > B, int n) { //variable to store answer int ans=0; //iterating over array for ( int i=0;i<n-1;i++) { for ( int j=i+1;j<n;j++) { //if found such element then increase answer if (A[i]+A[j]>B[i]+B[j])ans++; } } return ans; } // Driver code int main() { //size of array A and B int n = 5; vector< int > A; vector< int > B; A.push_back(4); A.push_back(8); A.push_back(2); A.push_back(6); A.push_back(2); B.push_back(4); B.push_back(5); B.push_back(4); B.push_back(1); B.push_back(3); cout << getPairs(A, B, n); return 0; } //code contributed by shubhamrajput6156 |
Java
// Java program to find the number of indices pair such that // pair sum from first Array is greater than second Array import java.util.*; public class Main { // Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] public static int getPairs( int [] A, int [] B, int n) { // variable to store answer int ans = 0 ; // iterating over array for ( int i = 0 ; i < n - 1 ; i++) { for ( int j = i + 1 ; j < n; j++) { // if found such element then increase // answer if (A[i] + A[j] > B[i] + B[j]) ans++; } } return ans; } // Driver code public static void main(String[] args) { // size of array A and B int n = 5 ; int [] A = { 4 , 8 , 2 , 6 , 2 }; int [] B = { 4 , 5 , 4 , 1 , 3 }; System.out.println(getPairs(A, B, n)); } } |
Python3
# Python 3 program to find the number of indices pair # such that pair sum from first Array # is greater than second Array # Function to get the number of pairs of indices # {i, j} in the given two arrays A and B such that # A[i] + A[j] > B[i] + B[j] def getPairs(A, B, n): # variable to store answer ans = 0 for i in range (n - 1 ): for j in range (i + 1 , n): # if found such element then increase answer if A[i] + A[j] > B[i] + B[j]: ans + = 1 return ans #driver code n = 5 A = [] A.append( 4 ) A.append( 8 ) A.append( 2 ) A.append( 6 ) A.append( 2 ) B = [] B.append( 4 ) B.append( 5 ) B.append( 4 ) B.append( 1 ) B.append( 3 ) print (getPairs(A, B, n)) # This code is contributed by redmoonz. |
C#
// C# program to find the number of indices pair such that // pair sum from first Array is greater than second Array using System; using System.Collections.Generic; public class GFG { // Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] static int GetPairs(List< int > A, List< int > B, int n) { // variable to store answer int ans = 0; // iterating over array for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { // if found such element then increase // answer if (A[i] + A[j] > B[i] + B[j]) { ans++; } } } return ans; } // Driver code static public void Main( string [] args) { // size of array A and B int n = 5; List< int > A = new List< int >{ 4, 8, 2, 6, 2 }; List< int > B = new List< int >{ 4, 5, 4, 1, 3 }; Console.WriteLine(GetPairs(A, B, n)); } } // This Code is Contributed by Prasad Kandekar(prasad264) |
Javascript
// Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] function getPairs(A, B, n) { // variable to store answer let ans = 0; // iterating over array for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { // if found such element then increase answer if (A[i] + A[j] > B[i] + B[j]) ans++; } } return ans; } // Driver code function main() { // size of array A and B let n = 5; let A = [ 4, 8, 2, 6, 2 ]; let B = [ 4, 5, 4, 1, 3 ]; console.log(getPairs(A, B, n)); } main(); |
Output:- 7
Time Complexity:- O(N^2)
Space Complexity:- O(1)
Efficient Approach: The key observation from the problem is that the given condition can also be visualised as (ai-bi) + (aj-bj)> 0 so we can make another array to store the difference of both arrays. let this array be D . Therefore, the problem reduces to finding pairs with Di+Dj>0. Now we can sort D array and for each corresponding element Di we will find the no of good pairs that Di can make and add this no of pairs to a count variable.For each element Di to find the no of good pairs it can make we can use the upper_bound function of the standard template library to find the upper bound of -Di. since the array is sorted so all elements present after -Di will also make good pair with Di .thus,if upper bound of -Di is x and n be the total size of array then total pairs corresponding to Di will be n-x. This approach takes O(NlogN) time.
- The given condition in the question can be rewritten as:
A[i] + A[j] > B[i] + B[j]
A[i] + A[j] - B[i] - B[j] > 0
(A[i] - B[i]) + (A[j] - B[j]) > 0
- Create another array, say D, to store the difference between elements at the corresponding index in both array, i.e.
- If we carefully look at the last condition ( (A[i] – B[i]) + (A[j] – B[j]) > 0 ) then it is quite obvious that the given condition i<j is trivial and non significant. Therefore, now we only have to find pairs in D such that their sum is > 0.
D[i] = A[i] - B[i]
- Now to make sure that the constraint i < j is satisfied, sort the difference array D, so that each element i is smaller than elements to its right.
- If at some index i, the value in the difference array D is negative, then we only need to find the nearest position ‘j’ at which the value is just greater than -D[i], so that on summation the value becomes > 0.
Inorder to find such index ‘j’, upper_bound() function or Binary Search can be used, since the array is sorted. - If at some index i, the value in array D is positive, then that means all the values after it will be positive as well. Therefore total no. of pair from index i to n-1 will be equal to n-i-1.
Below is the implementation of the above approach:
C++
// C++ program to find the number of indices pair // such that pair sum from first Array // is greater than second Array #include <bits/stdc++.h> using namespace std; // Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] int getPairs(vector< int > A, vector< int > B, int n) { // Initializing the difference array D vector< int > D(n); // Computing the difference between the // elements at every index and storing // it in the array D for ( int i = 0; i < n; i++) { D[i] = A[i] - B[i]; } // Sort the array D sort(D.begin(), D.end()); // Variable to store the total // number of pairs that satisfy // the given condition long long total = 0; // Loop to iterate through the difference // array D and find the total number // of pairs of indices that follow the // given condition for ( int i = 0; i < n; ++i) { // If the value at that index is negative or zero // then we need to find the index of the // value just greater than -D[i] if (D[i] <= 0) { int k = upper_bound(D.begin(), D.end(), -D[i]) - D.begin(); total += n - k; } // If the value at the index is positive // then we need to find the number of indexes after i-th index else { total += n-i-1; } } return total; } // Driver code int main() { int n = 5; vector< int > A; vector< int > B; A.push_back(4); A.push_back(8); A.push_back(2); A.push_back(6); A.push_back(2); B.push_back(4); B.push_back(5); B.push_back(4); B.push_back(1); B.push_back(3); cout << getPairs(A, B, n); } // This code is contributed by Udit Mehta |
Java
// Java program to find the number of indices pair // such that pair sum from first Array // is greater than second Array import java.util.*; class GFG{ // Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] static long getPairs(Vector<Integer> A, Vector<Integer> B, int n) { // Initializing the difference array D int []D = new int [n]; // Computing the difference between the // elements at every index and storing // it in the array D for ( int i = 0 ; i < n; i++) { D[i] = A.get(i) - B.get(i); } // Sort the array D Arrays.sort(D); // Variable to store the total // number of pairs that satisfy // the given condition long total = 0 ; // Loop to iterate through the difference // array D and find the total number // of pairs of indices that follow the // given condition for ( int i = 0 ; i < n; ++i) { // If the value at that index is negative or zero // then we need to find the index of the // value just greater than -D[i] if (D[i] <= 0 ) { int k = upper_bound(D, 0 ,D.length, -D[i]); total += n - k; } // If the value at the index is positive // then we need to find the number of indexes after i-th index else { total += n-i- 1 ; } } return total; } static int upper_bound( int [] a, int low, int high, int element) { while (low < high){ int middle = low + (high - low)/ 2 ; if (a[middle] > element) high = middle; else low = middle + 1 ; } return low; } // Driver code public static void main(String[] args) { int n = 5 ; Vector<Integer> A = new Vector<Integer>(); Vector<Integer> B= new Vector<Integer>(); A.add( 4 ); A.add( 8 ); A.add( 2 ); A.add( 6 ); A.add( 2 ); B.add( 4 ); B.add( 5 ); B.add( 4 ); B.add( 1 ); B.add( 3 ); System.out.print(getPairs(A, B, n)); } } // This code is contributed by Udit Mehta |
Python3
# Python 3 program to find the number of indices pair # such that pair sum from first Array # is greater than second Array import bisect # Function to get the number of pairs of indices # {i, j} in the given two arrays A and B such that # A[i] + A[j] > B[i] + B[j] def getPairs(A, B, n): # Initializing the difference array D D = [ 0 ] * (n) # Computing the difference between the # elements at every index and storing # it in the array D for i in range (n): D[i] = A[i] - B[i] # Sort the array D D.sort() # Variable to store the total # number of pairs that satisfy # the given condition total = 0 # Loop to iterate through the difference # array D and find the total number # of pairs of indices that follow the # given condition for i in range ( 0 ,n): # If the value at that index is negative # then we need to find the index of the # value just greater than -D[i] if (D[i] < = 0 ): k = bisect.bisect_right(D, - D[i], 0 , len (D)) total + = n - k # If the value at the index i is positive, # then we need to find the number of indexes after i-th index else : total + = n - i - 1 return total # Driver code if __name__ = = "__main__" : n = 5 A = [] B = [] A.append( 4 ); A.append( 8 ); A.append( 2 ); A.append( 6 ); A.append( 2 ); B.append( 4 ); B.append( 5 ); B.append( 4 ); B.append( 1 ); B.append( 3 ); print (getPairs(A, B, n)) # This code is contributed by Udit Mehta |
C#
// C# program to find the number of indices pair // such that pair sum from first Array // is greater than second Array using System; using System.Collections.Generic; class GFG{ // Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] static long getPairs(List< int > A, List< int > B, int n) { // Initializing the difference array D int []D = new int [n]; // Computing the difference between the // elements at every index and storing // it in the array D for ( int i = 0; i < n; i++) { D[i] = A[i] - B[i]; } // Sort the array D Array.Sort(D); // Variable to store the total // number of pairs that satisfy // the given condition long total = 0; // Loop to iterate through the difference // array D and find the total number // of pairs of indices that follow the // given condition for ( int i = 0; i < n; ++i) { // If the value at that index is negative or zero // then we need to find the index of the // value just greater than -D[i] if (D[i] <= 0) { int k = upper_bound(D,0,D.Length, -D[i]); total += n - k; } // If the value at the index is positive // then we need to find the number of indexes after i-th index else { total += n-i-1; } } return total; } static int upper_bound( int [] a, int low, int high, int element) { while (low < high){ int middle = low + (high - low)/2; if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Driver code public static void Main(String[] args) { int n = 5; List< int > A = new List< int >(); List< int > B= new List< int >(); A.Add(4); A.Add(8); A.Add(2); A.Add(6); A.Add(2); B.Add(4); B.Add(5); B.Add(4); B.Add(1); B.Add(3); Console.Write(getPairs(A, B, n)); } } // This code is contributed by Udit Mehta |
Javascript
<script> // Javascript program to find the number of indices pair // such that pair sum from first Array // is greater than second Array // Function to get the number of pairs of indices // {i, j} in the given two arrays A and B such that // A[i] + A[j] > B[i] + B[j] function getPairs(A, B, n) { // Initializing the difference array D let D = new Array(n); // Computing the difference between the // elements at every index and storing // it in the array D for (let i = 0; i < n; i++) { D[i] = A[i] - B[i]; } // Sort the array D D.sort((a, b) => a - b); // Variable to store the total // number of pairs that satisfy // the given condition let total = 0; // Loop to iterate through the difference // array D and find the total number // of pairs of indices that follow the // given condition for (int i = 0; i < n; ++i) { // If the value at that index is negative or zero // then we need to find the index of the // value just greater than -D[i] if (D[i] <= 0) { int k = upper_bound(D,0,D.length, -D[i]); total += n - k; } // If the value at the index is positive //then we need to find the number of indexes after i-th index else { total += n-i-1; } } return total; } function upper_bound(a, low, high, element) { while (low < high){ let middle = low + Math.floor((high - low)/2); if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Driver code let n = 5; let A = new Array(); let B = new Array(); A.push(4); A.push(8); A.push(2); A.push(6); A.push(2); B.push(4); B.push(5); B.push(4); B.push(1); B.push(3); document.write(getPairs(A, B, n)) </script> // This code is contributed by Udit Mehta |
7
Time Complexity Analysis:
- The sorting of the array takes O(N * log(N)) time.
- The time taken to find the index which is just greater than a specific value is O(Log(N)). Since in the worst case, this can be executed for N elements in the array, the overall time complexity for this is O(N * log(N)).
- Therefore, the overall time complexity is O(N * log(N)).