Count the divisors or multiples present in the Array for each element
Given an array A[] with N integers, for each integer A[i] in the array, the task is to find the number of integers A[j] (j != i) in the array such that A[i] % A[j] = 0 or A[j] % A[i] = 0.
Examples:
Input: A = {2, 3, 4, 5, 6}
Output: 2 1 1 0 2
Explanation:
For i=0, the valid indices are 2 and 4 as 4%2 = 0 and 6%2 = 0.
For i=1, the only valid index is 4 as 6%3 = 0.
For i=2, the only valid index is 0 as 4%2 = 0.
For i=3, there are no valid indices.
For i=0, the valid indices are 0 and 1 as 6%2 = 0 and 6%3 = 0.Input: A = {6, 6, 6, 6, 6}
Output: 4 4 4 4 4
Approach: The given problem can be solved by using the observation that the number of integers that satisfies the given condition can be categorized into two cases. Suppose the current integer is P and Q is an integer that satisfies the given conditions.
- Case 1 where Q is a multiple of P. Therefore, the count of integers in the given array that are divisible by P is the required answer. This case can be handled using a simple modification of Sieve of Eratosthenes which is discussed here.
- Case 2 where P is a multiple of Q. Therefore, the count of integers in the given array that Q divides P is the required answer. This case can be handled similarly using sieve as that of 1st Case.
So, the required answer for any integer is the sum of resulting integers of Case 1 and Case 2. In cases where P = Q, both Case 1 and Case 2 represents the same value and should be considered only once.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the count of integers // such that A[i]%A[j] = 0 or A[j]%A[i] = 0 // for each index of the array A[] void countIndex( int A[], int N) { // Stores the maximum integer in A[] int MAX = *max_element(A, A + N); // Stores the frequency of each // element in the array A[] vector< int > freq(MAX + 1, 0); for ( int i = 0; i < N; i++) freq[A[i]]++; // Stores the valid integers in A[] // for all integers from 1 to MAX vector< int > res(MAX + 1, 0); for ( int i = 1; i <= MAX; ++i) { for ( int j = i; j <= MAX; j += i) { // Case where P = Q if (i == j) { // Subtract 1 because P & Q // cannot have same index res[i] += (freq[j] - 1); } else { // Case 1 res[i] += freq[j]; // Case 2 res[j] += freq[i]; } } } // Loop to print answer for // each index of array A[] for ( int i = 0; i < N; i++) { cout << res[A[i]] << " " ; } } // Driver Code int main() { int A[] = { 2, 3, 4, 5, 6 }; int N = sizeof (A) / sizeof ( int ); // Function Call countIndex(A, N); return 0; } |
Java
// Java Program for the above approach import java.util.*; class GFG{ // Function to find the count of integers // such that A[i]%A[j] = 0 or A[j]%A[i] = 0 // for each index of the array []A static void countIndex( int []A, int N) { // Stores the maximum integer in []A int MAX = Arrays.stream(A).max().getAsInt(); // Stores the frequency of each // element in the array []A int []freq = new int [MAX + 1 ]; for ( int i = 0 ; i < N; i++) freq[A[i]]++; // Stores the valid integers in []A // for all integers from 1 to MAX int []res = new int [MAX + 1 ]; for ( int i = 1 ; i <= MAX; ++i) { for ( int j = i; j <= MAX; j += i) { // Case where P = Q if (i == j) { // Subtract 1 because P & Q // cannot have same index res[i] += (freq[j] - 1 ); } else { // Case 1 res[i] += freq[j]; // Case 2 res[j] += freq[i]; } } } // Loop to print answer for // each index of array []A for ( int i = 0 ; i < N; i++) { System.out.print(res[A[i]]+ " " ); } } // Driver Code public static void main(String[] args) { int []A = { 2 , 3 , 4 , 5 , 6 }; int N = A.length; // Function Call countIndex(A, N); } } // This code is contributed by Princi Singh |
Python3
# Python 3 Program for the above approach # Function to find the count of integers # such that A[i]%A[j] = 0 or A[j]%A[i] = 0 # for each index of the array A[] def countIndex(A, N): # Stores the maximum integer in A[] MAX = max (A) # Stores the frequency of each # element in the array A[] freq = [ 0 for i in range ( MAX + 1 )] for i in range (N): if freq[A[i]] > 0 : freq[A[i]] + = 1 else : freq[A[i]] = 1 # Stores the valid integers in A[] # for all integers from 1 to MAX res = [ 0 for i in range ( MAX + 1 )] for i in range ( 1 , MAX + 1 , 1 ): for j in range (i, MAX + 1 , i): # Case where P = Q if (i = = j): # Subtract 1 because P & Q # cannot have same index res[i] + = (freq[j] - 1 ) else : # Case 1 res[i] + = freq[j] # Case 2 res[j] + = freq[i] # Loop to print answer for # each index of array A[] for i in range (N): print (res[A[i]],end = " " ) # Driver Code if __name__ = = '__main__' : A = [ 2 , 3 , 4 , 5 , 6 ] N = len (A) # Function Call countIndex(A, N) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program of above approach using System; public class GFG { static void countIndex( int [] A, int N) { // Stores the maximum integer in []A int MAX = A[0]; for ( int i = 1; i < N; i++) { if (A[i] > MAX) { MAX = A[i]; } } // Stores the frequency of each // element in the array []A int [] freq = new int [MAX + 1]; for ( int i = 0; i < N; i++) freq[A[i]]++; // Stores the valid integers in []A // for all integers from 1 to MAX int [] res = new int [MAX + 1]; for ( int i = 1; i <= MAX; ++i) { for ( int j = i; j <= MAX; j += i) { // Case where P = Q if (i == j) { // Subtract 1 because P & Q // cannot have same index res[i] += (freq[j] - 1); } else { // Case 1 res[i] += freq[j]; // Case 2 res[j] += freq[i]; } } } // Loop to print answer for // each index of array []A for ( int i = 0; i < N; i++) { Console.Write(res[A[i]] + " " ); } } // Driver Code static public void Main() { int [] A = { 2, 3, 4, 5, 6 }; int N = A.Length; // Function Call countIndex(A, N); } } // This code is contributed by maddler. |
Javascript
<script> // JavaScript program for the above approach; // Function to find the count of integers // such that A[i]%A[j] = 0 or A[j]%A[i] = 0 // for each index of the array A[] function max_element(A, N) { let MAX = Number.MIN_VALUE; for (let i = 0; i < A.length; i++) { if (A[i] > MAX) { MAX = A[i]; } } return MAX; } function countIndex(A, N) { // Stores the maximum integer in A[] let MAX = max_element(A, A + N); // Stores the frequency of each // element in the array A[] let freq = new Array(MAX + 1).fill(0); for (let i = 0; i < N; i++) freq[A[i]]++; // Stores the valid integers in A[] // for all integers from 1 to MAX let res = new Array(MAX + 1).fill(0); for (let i = 1; i <= MAX; ++i) { for (let j = i; j <= MAX; j += i) { // Case where P = Q if (i == j) { // Subtract 1 because P & Q // cannot have same index res[i] += (freq[j] - 1); } else { // Case 1 res[i] += freq[j]; // Case 2 res[j] += freq[i]; } } } // Loop to print answer for // each index of array A[] for (let i = 0; i < N; i++) { document.write(res[A[i]] + " " ); } } // Driver Code let A = [2, 3, 4, 5, 6]; let N = A.length; // Function Call countIndex(A, N); // This code is contributed by Potta Lokesh </script> |
2 1 1 0 2
Time Complexity: O(N*log N)
Auxiliary Space: O(MAX) where MAX represents the maximum integer in the given array.
Contact Us