Given an array of integers arr, the task is to calculate the number of pairs (i, j) where i < j such that arr[j] % arr[i] = 0.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 5
Input: arr[] = {1, 1, 2, 2, 3, 3}
Output: 11
Approach 1:
Iterate over all pairs of the array and keep incrementing the count of pairs that satisfy the required condition.
Below code is the implementation of the above approach:
C++
// C++ Program to find// the number of pairs// (i, j) such that arr[i]// is a factor of arr[j]#include <bits/stdc++.h>using namespace std;// Function to return the// count of Pairsint numPairs(int arr[], int n){ int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[j] % arr[i] == 0) ans++; } } return ans;}// Driver codeint main(){ int arr[] = { 1, 1, 2, 2, 3, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << numPairs(arr, n) << endl; return 0;} |
Java
// Java Program to find the number of pairs// (i, j) such that arr[i] is a factor of arr[j]import java.util.*;import java.lang.*;class GFG{// Function to return the// count of Pairsstatic int numPairs(int arr[], int n){ int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (arr[j] % arr[i] == 0) ans++; } } return ans;}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 1, 2, 2, 3, 3 }; int n = arr.length; System.out.println(numPairs(arr, n));}}// This code is contributed by offbeat |
Python3
# Python3 program to find the number# of pairs (i, j) such that arr[i] # is a factor of arr[j] # Function to return the # count of Pairs def numPairs(arr, n): ans = 0 for i in range(n): for j in range(i + 1, n): if arr[j] % arr[i] == 0: ans += 1 return ans # Driver code arr = [ 1, 1, 2, 2, 3, 3 ] n = len(arr) print(numPairs(arr, n)) # This code is contributed by divyamohan123 |
C#
// C# Program to find the number of pairs// (i, j) such that arr[i] is a factor of arr[j]using System;class GFG{// Function to return the// count of Pairsstatic int numPairs(int []arr, int n){ int ans = 0; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { if (arr[j] % arr[i] == 0) ans++; } } return ans;}// Driver codepublic static void Main(){ int []arr = { 1, 1, 2, 2, 3, 3 }; int n = arr.Length; Console.Write(numPairs(arr, n));}}// This code is contributed by Code_Mech |
Javascript
<script> // Javascript Program to find // the number of pairs // (i, j) such that arr[i] // is a factor of arr[j] // Function to return the // count of Pairs function numPairs(arr, n) { let ans = 0; for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if (arr[j] % arr[i] == 0) ans++; } } return ans; } let arr = [ 1, 1, 2, 2, 3, 3 ]; let n = arr.length; document.write(numPairs(arr, n)); </script> |
Output:
11
Approach 2: Store the indices of all array elements in a map. Traverse the map and for every occurrence of an element:
- Add the occurrences of the same element after the current occurrence.
- Add the occurrences of all its multiples after the current occurrence using upper_bound
Below code is the implementation of the above approach:
C++
// C++ Program to find// the number of pairs// (i, j) such that arr[i]// is a factor of arr[j]#include <bits/stdc++.h>using namespace std;// Function to return the// count of Pairsint numPairs(int arr[], int n){ map<int, vector<int> > mp; int mx = 0; for (int i = 0; i < n; i++) { // Update the maximum mx = max(mx, arr[i]); // Store the indices of // every element mp[arr[i]].push_back(i); } int ans = 0; for (auto i : mp) { int ctr = 1; // Access all indices of i for (int j : i.second) { // Add the number of // occurrences of i // after j-th index ans += i.second.size() - ctr; // Traverse all multiples of i for (int k = 2 * i.first; k <= mx; k += i.first) { // Find their occurrences // after the j-th index int numGreater = 0; if (mp.find(k) != mp.end()) numGreater = int( mp[k] .end() - upper_bound( mp[k].begin(), mp[k].end(), j)); // Add the count ans += numGreater; } ctr++; } } return ans;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << numPairs(arr, n) << endl; return 0;} |
Java
// Java Program to find// the number of pairs// (i, j) such that arr[i]// is a factor of arr[j]import java.util.*;class GFG { static int upper_bound(ArrayList<Integer> arr, int ele) { for (int i = 0; i < arr.size(); i++) if (arr.get(i) > ele) return i; return arr.size(); } // Function to return the // count of Pairs static int numPairs(int[] arr, int n) { HashMap<Integer, ArrayList<Integer> > mp = new HashMap<Integer, ArrayList<Integer> >(); int mx = 0; for (int i = 0; i < n; i++) { // Update the maximum mx = Math.max(mx, arr[i]); // Store the indices of // every element ArrayList<Integer> l1; if (!mp.containsKey(arr[i])) l1 = new ArrayList<Integer>(); else l1 = mp.get(arr[i]); l1.add(i); mp.put(arr[i], l1); } int ans = 0; for(var i : mp.entrySet()) { int ctr = 1; // Access all indices of i for (int j : i.getValue()) { // Add the number of // occurrences of i // after j-th index ans += (i.getValue()).size() - ctr; // Traverse all multiples of i for (int k = 2 * i.getKey(); k <= mx; k += i.getKey()) { // Find their occurrences // after the j-th index int numGreater = 0; if (mp.containsKey(k)) numGreater = mp.get(k).size() - upper_bound(mp.get(k), j); // Add the count ans += numGreater; } ctr++; } } return ans; } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int n = arr.length; System.out.println(numPairs(arr, n)); }}// This code is contributed by phasing17. |
Python3
# Python3 Program to find# the number of pairs# (i, j) such that arr[i]# is a factor of arr[j]def upper_bound(arr, ele): for i in range(len(arr)): if (arr[i] > ele): return i; return len(arr)# Function to return the# count of Pairsdef numPairs(arr, n): mp = dict(); mx = 0; for i in range(n): # Update the maximum mx = max(mx, arr[i]); # Store the indices of # every element if arr[i] not in mp: mp[arr[i]] = [] mp[arr[i]].append(i); ans = 0; for first, second in mp.items(): ctr = 1; # Access all indices of i for j in second: # Add the number of # occurrences of i # after j-th index ans += len(second) - ctr; # Traverse all multiples of i for k in range(2 * first, mx + 1, first): # Find their occurrences # after the j-th index numGreater = 0; if k in mp: numGreater = (len(mp[k]) - upper_bound(mp[k], j)); # Add the count ans += numGreater; ctr += 1; return ans;# Driver codearr = [ 1, 2, 3, 4, 5 ];n = len(arr);print(numPairs(arr, n)) # This code is contributed by phasing17 |
C#
// C# Program to find// the number of pairs// (i, j) such that arr[i]// is a factor of arr[j]using System;using System.Collections.Generic;class GFG { static int upper_bound(List<int> arr, int ele) { for (var i = 0; i < arr.Count; i++) if (arr[i] > ele) return i; return arr.Count; } // Function to return the // count of Pairs static int numPairs(int[] arr, int n) { Dictionary<int, List<int> > mp = new Dictionary<int, List<int> >(); int mx = 0; for (int i = 0; i < n; i++) { // Update the maximum mx = Math.Max(mx, arr[i]); // Store the indices of // every element if (!mp.ContainsKey(arr[i])) mp[arr[i]] = new List<int>(); mp[arr[i]].Add(i); } int ans = 0; foreach(var i in mp) { int ctr = 1; // Access all indices of i foreach(int j in i.Value) { // Add the number of // occurrences of i // after j-th index ans += (i.Value).Count - ctr; // Traverse all multiples of i for (int k = 2 * i.Key; k <= mx; k += i.Key) { // Find their occurrences // after the j-th index int numGreater = 0; if (mp.ContainsKey(k)) numGreater = mp[k].Count - upper_bound(mp[k], j); // Add the count ans += numGreater; } ctr++; } } return ans; } // Driver code public static void Main(string[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int n = arr.Length; Console.WriteLine(numPairs(arr, n)); }}// This code is contributed by phasing17. |
Javascript
// JS Program to find// the number of pairs// (i, j) such that arr[i]// is a factor of arr[j]function upper_bound(arr, ele){ for (var i = 0; i < arr.length; i++) if (arr[i] > ele) return i; return arr.length;}// Function to return the// count of Pairsfunction numPairs(arr, n){ let mp = {}; let mx = 0; for (let i = 0; i < n; i++) { // Update the maximum mx = Math.max(mx, arr[i]); // Store the indices of // every element if (!mp.hasOwnProperty(arr[i])) mp[arr[i]] = [] mp[arr[i]].push(i); } let ans = 0; for (let [first, second] of Object.entries(mp)) { first = parseInt(first) let ctr = 1; // Access all indices of i for (let j of second) { // Add the number of // occurrences of i // after j-th index ans += second.length - ctr; // Traverse all multiples of i for (let k = 2 * first; k <= mx; k += first) { // Find their occurrences // after the j-th index let numGreater = 0; if (mp.hasOwnProperty(k)) numGreater = parseInt(mp[k].length - upper_bound(mp[k], j)); // Add the count ans += numGreater; } ctr++; } } return ans;}// Driver codelet arr = [ 1, 2, 3, 4, 5 ];let n = arr.length;console.log(numPairs(arr, n)) // This code is contributed by phasing17 |
Output:
5
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!
