Number of pairs in an array such that product is greater than sum
Given a array a[] of non-negative integers. Count the number of pairs (i, j) in the array such that a[i] + a[j] < a[i]*a[j]. (the pair (i, j) and (j, i) are considered same and i should not be equal to j)
Examples:
Input : a[] = {3, 4, 5} Output : 3 Pairs are (3, 4) , (4, 5) and (3,5) Input : a[] = {1, 1, 1} Output : 0
Naive approach: For each value a[i] count the number of a[j] (i > j) such that a[i]*a[j] > a[i] + a[j]
Implementation:
C++
// Naive C++ program to count number of pairs // such that their sum is more than product. #include<bits/stdc++.h> using namespace std; // Returns the number of valid pairs int countPairs ( int arr[], int n) { int ans = 0; // initializing answer // Traversing the array. For each array // element, checking its predecessors that // follow the condition for ( int i = 0; i<n; i++) for ( int j = i-1; j>= 0; j--) if (arr[i]*arr[j] > arr[i] + arr[j]) ans++; return ans; } // Driver function int main() { int arr[] = {3, 4, 5}; int n = sizeof (arr)/ sizeof (arr[0]); cout << countPairs(arr, n); return 0; } |
Java
// Naive java program to count number of pairs // such that their sum is more than product. import java.*; public class GFG { // Returns the number of valid pairs static int countPairs ( int arr[], int n) { int ans = 0 ; // initializing answer // Traversing the array. For each array // element, checking its predecessors that // follow the condition for ( int i = 0 ; i<n; i++) for ( int j = i- 1 ; j>= 0 ; j--) if (arr[i]*arr[j] > arr[i] + arr[j]) ans++; return ans; } // Driver code public static void main(String args[]) { int arr[] = { 3 , 4 , 5 }; int n = arr.length; System.out.println(countPairs(arr, n)); } } // This code is contributed by Sam007 |
Python3
# Naive Python program to count number # of pairs such that their sum is more # than product. # Returns the number of valid pairs def countPairs(arr, n): # initializing answer ans = 0 # Traversing the array. For each # array element, checking its # predecessors that follow the # condition for i in range ( 0 , n): j = i - 1 while (j > = 0 ): if (arr[i] * arr[j] > arr[i] + arr[j]): ans = ans + 1 j = j - 1 return ans # Driver program to test above function. arr = [ 3 , 4 , 5 ] n = len (arr) k = countPairs(arr, n) print (k) # This code is contributed by Sam007. |
C#
// Naive C# program to count number of pairs // such that their sum is more than product. using System; public class GFG { // Returns the number of valid pairs static int countPairs ( int []arr, int n) { int ans = 0; // initializing answer // Traversing the array. For each array // element, checking its predecessors that // follow the condition for ( int i = 0; i<n; i++) for ( int j = i-1; j>= 0; j--) if (arr[i]*arr[j] > arr[i] + arr[j]) ans++; return ans; } // driver program public static void Main() { int []arr = {3, 4, 5}; int n = arr.Length; Console.Write( countPairs(arr, n)); } } // This code is contributed by Sam007 |
PHP
<?php // Naive PHP program to // count number of pairs // such that their sum // is more than product. // Returns the number // of valid pairs function countPairs ( $arr , $n ) { // initializing answer $ans = 0; // Traversing the array. // For each array // element, checking // its predecessors that // follow the condition for ( $i = 0; $i < $n ; $i ++) for ( $j = $i - 1; $j >= 0; $j --) if ( $arr [ $i ] * $arr [ $j ] > $arr [ $i ] + $arr [ $j ]) $ans ++; return $ans ; } // Driver Code $arr = array (3, 4, 5); $n = sizeof( $arr ); echo (countPairs( $arr , $n )); // This code is contributed by Ajit. ?> |
Javascript
<script> // Naive Javascript program to count number of pairs // such that their sum is more than product. // Returns the number of valid pairs function countPairs(arr, n) { let ans = 0; // initializing answer // Traversing the array. For each array // element, checking its predecessors that // follow the condition for (let i = 0; i<n; i++) for (let j = i-1; j>= 0; j--) if (arr[i]*arr[j] > (arr[i] + arr[j])) ans++; return ans; } let arr = [3, 4, 5]; let n = arr.length; document.write( countPairs(arr, n)); </script> |
3
Efficient approach:
When a[i] = 0 : a[i]*a[j] = 0 and a[i] + a[j] >= 0 so if a[i] = 0 no pairs can be found.
When a[i] = 1 : a[i]*a[j] = a[j] and a[i] + a[j] = 1 + a[j], so no pairs can be found when a[i] = 1
When a[i] = 2 and a[j] = 2 : a[i]*a[j] = a[i] + a[j] = 4
When a[i] = 2 and a[j] > 2 or a[i] > 2 and a[j] >= 2 : All such pairs are valid.
To solve this problem, count the number of 2s in the array say twoCount. Count the numbers greater than 2 in the array say twoGreaterCount. Answer will be twoCount * twoGreaterCount + twoGreaterCount * (twoGreaterCount-1)/2
Implementation:
C++
// C++ implementation of efficient approach // to count valid pairs. #include<bits/stdc++.h> using namespace std; // returns the number of valid pairs int CountPairs ( int arr[], int n) { // traversing the array, counting the // number of 2s and greater than 2 // in array int twoCount = 0, twoGrCount = 0; for ( int i = 0; i<n; i++) { if (arr[i] == 2) twoCount++; else if (arr[i] > 2) twoGrCount++; } return twoCount*twoGrCount + (twoGrCount*(twoGrCount-1))/2; } // Driver function int main() { int arr[] = {3, 4, 5}; int n = sizeof (arr)/ sizeof (arr[0]); cout << CountPairs(arr, n); return 0; } |
Java
// Java implementation of efficient approach // to count valid pairs. import java.*; public class GFG { // Returns the number of valid pairs static int countPairs ( int arr[], int n) { // traversing the array, counting the // number of 2s and greater than 2 // in array int twoCount = 0 , twoGrCount = 0 ; for ( int i = 0 ; i<n; i++) { if (arr[i] == 2 ) twoCount++; else if (arr[i] > 2 ) twoGrCount++; } return twoCount*twoGrCount + (twoGrCount*(twoGrCount- 1 ))/ 2 ; } // Driver code public static void main(String args[]) { int arr[] = { 3 , 4 , 5 }; int n = arr.length; System.out.println(countPairs(arr, n)); } } // This code is contributed by Sam007 |
Python3
# python implementation of efficient approach # to count valid pairs. # returns the number of valid pairs def CountPairs (arr,n): # traversing the array, counting the # number of 2s and greater than 2 # in array twoCount = 0 twoGrCount = 0 for i in range ( 0 , n): if (arr[i] = = 2 ): twoCount + = 1 else if (arr[i] > 2 ): twoGrCount + = 1 return ((twoCount * twoGrCount) + (twoGrCount * (twoGrCount - 1 )) / 2 ) # Driver function arr = [ 3 , 4 , 5 ] n = len (arr) print ( CountPairs(arr, n)) # This code is contributed by Sam007. |
C#
// C# implementation of efficient approach // to count valid pairs. using System; public class GFG { // Returns the number of valid pairs static int countPairs ( int []arr, int n) { // traversing the array, counting the // number of 2s and greater than 2 // in array int twoCount = 0, twoGrCount = 0; for ( int i = 0; i<n; i++) { if (arr[i] == 2) twoCount++; else if (arr[i] > 2) twoGrCount++; } return twoCount*twoGrCount + (twoGrCount*(twoGrCount-1))/2; } // driver program public static void Main() { int []arr = {3, 4, 5}; int n = arr.Length; Console.Write( countPairs(arr, n)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation of // efficient approach // to count valid pairs. // returns the number // of valid pairs function CountPairs ( $arr , $n ) { // traversing the array, counting // the number of 2s and greater // than 2 in array $twoCount = 0; $twoGrCount = 0; for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] == 2) $twoCount ++; else if ( $arr [ $i ] > 2) $twoGrCount ++; } return $twoCount * $twoGrCount + ( $twoGrCount * ( $twoGrCount - 1)) / 2; } // Driver Code $arr = array (3, 4, 5); $n = sizeof( $arr ); echo (CountPairs( $arr , $n )); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript implementation of efficient approach to count valid pairs. // returns the number of valid pairs function CountPairs(arr, n) { // traversing the array, counting the // number of 2s and greater than 2 // in array let twoCount = 0, twoGrCount = 0; for (let i = 0; i<n; i++) { if (arr[i] == 2) twoCount++; else if (arr[i] > 2) twoGrCount++; } return twoCount*twoGrCount + parseInt((twoGrCount*(twoGrCount-1))/2, 10); } let arr = [3, 4, 5]; let n = arr.length; document.write(CountPairs(arr, n)); </script> |
3
Time Complexity: O(n)
Auxiliary Space: O(1)