Given an array arr[], the task is to find the count of pairs in the array such that LCM(arr[i], arr[j]) > min(arr[i], arr[j])
Note: Pairs (arr[i], arr[j]) and (arr[j], arr[i]) are considered identical and will be counted only once.
Examples:
Input: arr[] = {1, 1, 4, 9}
Output: 5
All valid pairs are (1, 4), (1, 9), (1, 4), (1, 9) and (4, 9).Input: arr[] = {2, 4, 5, 2, 5, 7, 2, 8}
Output: 24
Naive approach:
- Generate all the pair
- Check the given condition LCM(arr[i], arr[j]) > min(arr[i], arr[j])
- If true, then increment the count by 1.
- Check the given condition LCM(arr[i], arr[j]) > min(arr[i], arr[j])
- Finally, return count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the lcm of two numberint lcm(int a, int b) { return (a / __gcd(a, b)) * b; }// Function to return the count of valid pairsint count_pairs(int n, int arr[]){ int count = 0; // Generate all the pair for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check the given condition. // If true, then increment the count by 1. if (lcm(arr[i], arr[j]) > min(arr[i], arr[j])) count++; } } // Finally return count. return count;}// Driver Codeint main(){ int arr[] = { 2, 4, 5, 2, 5, 7, 2, 8 }; int n = sizeof(arr) / sizeof(arr[0]); cout << count_pairs(n, arr); return 0;} |
Java
// Java implementation of the approachimport java.util.*;public class GFG { // Function to find the lcm of two number static int lcm(int a, int b) { return (a / gcd(a, b)) * b; } static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to return the count of valid pairs static int count_pairs(int n, int arr[]) { int count = 0; // Generate all the pair for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check the given condition. // If true, then increment the count by 1. if (lcm(arr[i], arr[j]) > Math.min(arr[i], arr[j])) count++; } } // Finally return count. return count; } // Driver Code public static void main(String[] args) { int arr[] = { 2, 4, 5, 2, 5, 7, 2, 8 }; int n = arr.length; System.out.println(count_pairs(n, arr)); }}// This code is contributed by Karandeep1234 |
Python3
# python implementation of the approachimport math # Function to find the lcm of two numberdef lcm(a, b): return (a / math.gcd(a, b)) * b;# Function to return the count of valid pairsdef count_pairs(n, arr): count = 0; # Generate all the pair for i in range(0,n): for j in range(i+1, n): # Check the given condition. # If true, then increment the count by 1. if (lcm(arr[i], arr[j]) > min(arr[i], arr[j])): count+=1; # Finally return count. return count;# Driver Codearr = [ 2, 4, 5, 2, 5, 7, 2, 8 ];n = len(arr);print(count_pairs(n, arr)); |
C#
// C# implementation of the approachusing System;using System.Linq;using System.Collections.Generic;class GFG { static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Function to find the lcm of two number static int lcm(int a, int b) { return (a / __gcd(a, b)) * b; } // Function to return the count of valid pairs static int count_pairs(int n, int[] arr) { int count = 0; // Generate all the pair for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Check the given condition. // If true, then increment the count by 1. if (lcm(arr[i], arr[j]) > Math.Min(arr[i], arr[j])) count++; } } // Finally return count. return count; } // Driver Code public static void Main() { int[] arr = { 2, 4, 5, 2, 5, 7, 2, 8 }; int n = arr.Length; Console.Write(count_pairs(n, arr)); } } |
Javascript
// Javascript implementation of the approach//Function to find gcd of two numberfunction __gcd(a, b){ if(b==0) return a; return __gcd(b, a%b);}// Function to find the lcm of two numberfunction lcm(a, b) { return (a / __gcd(a, b)) * b; }// Function to return the count of valid pairsfunction count_pairs(n, arr){ let count = 0; // Generate all the pair for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // Check the given condition. // If true, then increment the count by 1. if (lcm(arr[i], arr[j]) > Math.min(arr[i], arr[j])) count++; } } // Finally return count. return count;}// Driver Code let arr = [2, 4, 5, 2, 5, 7, 2, 8 ]; let n = arr.length; document.write(count_pairs(n, arr)); |
Output
24
Time Complexity: O(n2*log(m)), where n and m are the length of the given array arr and maximum element in the array respectively.
Auxiliary Space: O(1)
Approach: It is observed that only the pairs of the form (arr[i], arr[j]) where arr[i] = arr[j] won’t satisfy the given condition. So, the problem now gets reduced to finding the number of pairs (arr[i], arr[j]) such that arr[i] != arr[j].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of valid pairsint count_pairs(int n, int a[]){ // Store frequencies of array elements unordered_map<int, int> frequency; for (int i = 0; i < n; i++) { frequency[a[i]]++; } int count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] for (auto x : frequency) { int f = x.second; count += f * (f - 1) / 2; } // Count of pairs (arr[i], arr[j]) where // arr[i] != arr[j], i.e. Total pairs - pairs // where arr[i] = arr[j] return ((n * (n - 1)) / 2) - count;}// Driver Codeint main(){ int arr[] = { 2, 4, 5, 2, 5, 7, 2, 8 }; int n = sizeof(arr) / sizeof(arr[0]); cout << count_pairs(n, arr); return 0;} |
Java
// Java implementation of the approachimport java.util.HashMap;import java.util.Map;class GfG{ // Function to return the count of valid pairs static int count_pairs(int n, int a[]) { // Store frequencies of array elements HashMap<Integer, Integer> frequency = new HashMap<>(); for (int i = 0; i < n; i++) { if (!frequency.containsKey(a[i])) frequency.put(a[i], 0); frequency.put(a[i], frequency.get(a[i])+1); } int count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] for (Map.Entry<Integer, Integer> x: frequency.entrySet()) { int f = x.getValue(); count += f * (f - 1) / 2; } // Count of pairs (arr[i], arr[j]) where // arr[i] != arr[j], i.e. Total pairs - pairs // where arr[i] = arr[j] return ((n * (n - 1)) / 2) - count; } // Driver code public static void main(String []args) { int arr[] = { 2, 4, 5, 2, 5, 7, 2, 8 }; int n = arr.length; System.out.println(count_pairs(n, arr)); }} // This code is contributed by Rituraj Jain |
Python3
# Python3 implementation of the approach # Function to return the count # of valid pairs def count_pairs(n, a) : # Store frequencies of array elements frequency = dict.fromkeys(a, 0) for i in range(n) : frequency[a[i]] += 1 count = 0 # Count of pairs (arr[i], arr[j]) # where arr[i] = arr[j] for f in frequency.values() : count += f * (f - 1) // 2 # Count of pairs (arr[i], arr[j]) where # arr[i] != arr[j], i.e. Total pairs - pairs # where arr[i] = arr[j] return ((n * (n - 1)) // 2) - count# Driver Code if __name__ == "__main__" : arr = [ 2, 4, 5, 2, 5, 7, 2, 8 ] n = len(arr) print(count_pairs(n, arr))# This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GfG{ // Function to return the count of valid pairs static int count_pairs(int n, int []arr) { // Store frequencies of array elements Dictionary<int,int> mp = new Dictionary<int,int>(); for (int i = 0 ; i < n; i++) { if(mp.ContainsKey(arr[i])) { var val = mp[arr[i]]; mp.Remove(arr[i]); mp.Add(arr[i], val + 1); } else { mp.Add(arr[i], 1); } } int count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] foreach(KeyValuePair<int, int> x in mp) { int f = x.Value; count += f * (f - 1) / 2; } // Count of pairs (arr[i], arr[j]) where // arr[i] != arr[j], i.e. Total pairs - pairs // where arr[i] = arr[j] return ((n * (n - 1)) / 2) - count; } // Driver code public static void Main(String []args) { int []arr = { 2, 4, 5, 2, 5, 7, 2, 8 }; int n = arr.Length; Console.WriteLine(count_pairs(n, arr)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of valid pairsfunction count_pairs(n, a){ // Store frequencies of array elements var frequency = new Map(); for (var i = 0; i < n; i++) { if(frequency.has(a[i])) frequency.set(a[i], frequency.get(a[i])+1) else frequency.set(a[i], 1) } var count = 0; // Count of pairs (arr[i], arr[j]) // where arr[i] = arr[j] frequency.forEach((value, key) => { var f = value; count += f * (f - 1) / 2; }); // Count of pairs (arr[i], arr[j]) where // arr[i] != arr[j], i.e. Total pairs - pairs // where arr[i] = arr[j] return ((n * (n - 1)) / 2) - count;}// Driver Codevar arr = [2, 4, 5, 2, 5, 7, 2, 8];var n = arr.length;document.write( count_pairs(n, arr));</script> |
Output
24
Complexity Analysis:
- Time Complexity: O(n), where n represents the size of the given array.
- Auxiliary Space: O(n), where n represents the size of the given array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
