Count of multiples in an Array before every element
Given an array arr of size N, the task is to count the number of indices j (j<i) such that a[i] divides a[j], for all valid indexes i.
Examples:
Input: arr[] = {8, 1, 28, 4, 2, 6, 7}
Output: 0, 1, 0, 2, 3, 0, 1
No of multiples for each element before itself –
N(8) = 0 ()
N(1) = 1 (8)
N(28) = 0 ()
N(4) = 2 (28, 8)
N(2) = 3 (4, 28, 8)
N(6) = 0 ()
N(7) = 1 (28)
Input: arr[] = {1, 1, 1, 1}
Output: 0, 1, 2, 3
Naive Approach: Traverse through all valid indices j, in range [0, i-1], for each index i; and count the divisors for each indexes.
Time Complexity: O(N2)
Space Complexity: O(1)
Efficient Approach: This approach is to use map. Increment the count of factors in the map while traversing the array and lookup for that count in the map to find all valid j (< i) without traversing back.
Below is the implementation of the above approach.
C++
// C++ program to count of multiples// in an Array before every element#include <bits/stdc++.h>using namespace std;// Function to find all factors of N// and keep their count in mapvoid add_factors(int n, unordered_map<int, int>& mp){ // Traverse from 1 to sqrt(N) // if i divides N, // increment i and N/i in map for (int i = 1; i <= int(sqrt(n)); i++) { if (n % i == 0) { if (n / i == i) mp[i]++; else { mp[i]++; mp[n / i]++; } } }}// Function to count of multiples// in an Array before every elementvoid count_divisors(int a[], int n){ // To store factors all of all numbers unordered_map<int, int> mp; // Traverse for all possible i's for (int i = 0; i < n; i++) { // Printing value of a[i] in map cout << mp[a[i]] << " "; // Now updating the factors // of a[i] in the map add_factors(a[i], mp); }}// Driver codeint main(){ int arr[] = { 8, 1, 28, 4, 2, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call count_divisors(arr, n); return 0;} |
Java
// Java program to count of multiples// in an Array before every elementimport java.util.*;class GFG{ // Function to find all factors of N// and keep their count in mapstatic void add_factors(int n, HashMap<Integer,Integer> mp){ // Traverse from 1 to Math.sqrt(N) // if i divides N, // increment i and N/i in map for (int i = 1; i <= (Math.sqrt(n)); i++) { if (n % i == 0) { if (n / i == i) { if(mp.containsKey(i)) mp.put(i, mp.get(i) + 1); else mp.put(i, 1); } else { if(mp.containsKey(i)) mp.put(i, mp.get(i) + 1); else mp.put(i, 1); if(mp.containsKey(n / i)) mp.put(n / i, mp.get(n / i) + 1); else mp.put(n / i, 1); } } }} // Function to count of multiples// in an Array before every elementstatic void count_divisors(int a[], int n){ // To store factors all of all numbers HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Traverse for all possible i's for (int i = 0; i < n; i++) { // Printing value of a[i] in map System.out.print(mp.get(a[i]) == null ? 0 + " " : mp.get(a[i]) + " "); // Now updating the factors // of a[i] in the map add_factors(a[i], mp); }} // Driver codepublic static void main(String[] args){ int arr[] = { 8, 1, 28, 4, 2, 6, 7 }; int n = arr.length; // Function call count_divisors(arr, n); }}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program to count of multiples# in an Array before every elementfrom collections import defaultdictimport math # Function to find all factors of N# and keep their count in mapdef add_factors(n, mp): # Traverse from 1 to sqrt(N) # if i divides N, # increment i and N/i in map for i in range(1, int(math.sqrt(n)) + 1,): if (n % i == 0): if (n // i == i): mp[i] += 1 else : mp[i] += 1 mp[n // i] += 1 # Function to count of multiples# in an Array before every elementdef count_divisors(a, n): # To store factors all of all numbers mp = defaultdict(int) # Traverse for all possible i's for i in range(n) : # Printing value of a[i] in map print(mp[a[i]], end=" ") # Now updating the factors # of a[i] in the map add_factors(a[i], mp) # Driver codeif __name__ == "__main__": arr = [ 8, 1, 28, 4, 2, 6, 7 ] n = len(arr) # Function call count_divisors(arr, n) # This code is contributed by chitranayal |
C#
// C# program to count of multiples// in an Array before every elementusing System;using System.Collections.Generic;class GFG{ // Function to find all factors of N// and keep their count in mapstatic void add_factors(int n, Dictionary<int,int> mp){ // Traverse from 1 to Math.Sqrt(N) // if i divides N, // increment i and N/i in map for (int i = 1; i <= (Math.Sqrt(n)); i++) { if (n % i == 0) { if (n / i == i) { if(mp.ContainsKey(i)) mp[i] = mp[i] + 1; else mp.Add(i, 1); } else { if(mp.ContainsKey(i)) mp[i] = mp[i] + 1; else mp.Add(i, 1); if(mp.ContainsKey(n / i)) mp[n / i] = mp[n / i] + 1; else mp.Add(n / i, 1); } } }} // Function to count of multiples// in an Array before every elementstatic void count_divisors(int []a, int n){ // To store factors all of all numbers Dictionary<int,int> mp = new Dictionary<int,int>(); // Traverse for all possible i's for (int i = 0; i < n; i++) { // Printing value of a[i] in map Console.Write(!mp.ContainsKey(a[i]) ? 0 + " " : mp[a[i]] + " "); // Now updating the factors // of a[i] in the map add_factors(a[i], mp); }} // Driver codepublic static void Main(String[] args){ int []arr = { 8, 1, 28, 4, 2, 6, 7 }; int n = arr.Length; // Function call count_divisors(arr, n); }}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program to count of multiples// in an Array before every element// Function to find all factors of N// and keep their count in mapfunction add_factors(n, mp){ // Traverse from 1 to sqrt(N) // if i divides N, // increment i and N/i in map for (var i = 1; i <= parseInt(Math.sqrt(n)); i++) { if (n % i == 0) { if (parseInt(n / i) == i) { if(mp.has(i)) mp.set(i, mp.get(i)+1) else mp.set(i, 1) } else { if(mp.has(i)) mp.set(i, mp.get(i)+1) else mp.set(i, 1) if(mp.has(parseInt(n/i))) mp.set(parseInt(n/i), mp.get(parseInt(n/i))+1) else mp.set(parseInt(n/i), 1) } } } return mp;}// Function to count of multiples// in an Array before every elementfunction count_divisors(a, n){ // To store factors all of all numbers var mp = new Map(); // Traverse for all possible i's for (var i = 0; i < n; i++) { // Printing value of a[i] in map document.write( (mp.has(a[i])?mp.get(a[i]):0) + " "); // Now updating the factors // of a[i] in the map mp = add_factors(a[i], mp); }}// Driver codevar arr = [8, 1, 28, 4, 2, 6, 7];var n = arr.length;// Function callcount_divisors(arr, n);// This code is contributed by famously.</script> |
Output
0 1 0 2 3 0 1
Time Complexity: O(N * sqrt(val)), where N is the size of array and val is the maximum value of elements present in the array.
Auxiliary Space: O(N), as we are using extra space for map mp.
Approach 2: WIthout MAP:
In the code using maps, we use a defaultdict to keep track of the count of each factor for all numbers encountered so far. This allows us to avoid recomputing the factorization for each number in the input array. Instead, we can simply look up the count of factors for each element in the map and increment it as we encounter new multiples.
C++
#include <iostream>#include <cmath>#include <vector>using namespace std;// Function to find all factors of N// and return their countint count_factors(int n) { int count = 0; // Traverse from 1 to sqrt(N) // if i divides N, increment count for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { if (n / i == i) { count++; } else { count += 2; } } } return count;}// Function to count of multiples// in an Array before every elementvoid count_divisors(vector<int> a, int n) { // Traverse for all possible i's for (int i = 0; i < n; i++) { // Count the number of multiples // of a[i] in the array int count = 0; for (int j = 0; j < i; j++) { if (a[j] % a[i] == 0) { count++; } } // Print the count cout << count << " "; }}// Driver codeint main() { vector<int> arr {8, 1, 28, 4, 2, 6, 7}; int n = arr.size(); // Function call count_divisors(arr, n); return 0;} |
Java
import java.util.*;public class Main { // Function to find all factors of N // and return their count public static int countFactors(int n) { int count = 0; // Traverse from 1 to sqrt(N) // if i divides N, increment count for (int i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { if (n / i == i) { count++; } else { count += 2; } } } return count; } // Function to count of multiples // in an Array before every element public static void countDivisors(List<Integer> a, int n) { // Traverse for all possible i's for (int i = 0; i < n; i++) { // Count the number of multiples // of a[i] in the array int count = 0; for (int j = 0; j < i; j++) { if (a.get(j) % a.get(i) == 0) { count++; } } // Print the count System.out.print(count + " "); } } // Driver code public static void main(String[] args) { List<Integer> arr = Arrays.asList(8, 1, 28, 4, 2, 6, 7); int n = arr.size(); // Function call countDivisors(arr, n); }} |
Python3
import math# Function to find all factors of N# and return their countdef count_factors(n): count = 0 # Traverse from 1 to sqrt(N) # if i divides N, increment count for i in range(1, int(math.sqrt(n)) + 1): if (n % i == 0): if (n // i == i): count += 1 else: count += 2 return count# Function to count of multiples# in an Array before every elementdef count_divisors(a, n): # Traverse for all possible i's for i in range(n): # Count the number of multiples # of a[i] in the array count = 0 for j in range(i): if a[j] % a[i] == 0: count += 1 # Print the count print(count, end=" ")# Driver codeif __name__ == "__main__": arr = [ 8, 1, 28, 4, 2, 6, 7 ] n = len(arr) # Function call count_divisors(arr, n) |
C#
using System;using System.Collections.Generic;namespace CountMultiples{class Program{// Function to find all factors of N// and return their countpublic static int CountFactors(int n){int count = 0; // Traverse from 1 to sqrt(N) // if i divides N, increment count for (int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { if (n / i == i) { count++; } else { count += 2; } } } return count; } // Function to count of multiples // in an Array before every element public static void CountDivisors(List<int> a, int n) { // Traverse for all possible i's for (int i = 0; i < n; i++) { // Count the number of multiples // of a[i] in the array int count = 0; for (int j = 0; j < i; j++) { if (a[j] % a[i] == 0) { count++; } } // Print the count Console.Write(count + " "); } } // Driver code static void Main(string[] args) { List<int> arr = new List<int> { 8, 1, 28, 4, 2, 6, 7 }; int n = arr.Count; // Function call CountDivisors(arr, n); }}} |
Javascript
// Function to find all factors of N// and return their countfunction count_factors(n) { let count = 0; // Traverse from 1 to sqrt(N) // if i divides N, increment count for (let i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { if (n / i == i) { count++; } else { count += 2; } } } return count;}// Function to count of multiples// in an Array before every elementfunction count_divisors(a, n) { // Traverse for all possible i's for (let i = 0; i < n; i++) { // Count the number of multiples // of a[i] in the array let count = 0; for (let j = 0; j < i; j++) { if (a[j] % a[i] == 0) { count++; } } // Print the count console.log(count + " "); }}// Driver codelet arr = [8, 1, 28, 4, 2, 6, 7];let n = arr.length;// Function callcount_divisors(arr, n); |
Output
0 1 0 2 3 0 1
Time Complexity: O(sqrt(n)), where N is the size of array and val is the maximum value of elements present in the array.
Auxiliary Space: O(N)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
