Given an array A[] of N integers, the task is to generate an array B[] such that B[i] contains the count of indices j in A[] such that j < i and A[j] % A[i] = 0
Examples:
Input: arr[] = {3, 5, 1}
Output: 0 0 2
Explanation:
3 and 5 do not divide any element on
their left but 1 divides 3 and 5.
Input: arr[] = {8, 1, 28, 4, 2, 6, 7}
Output: 0 1 0 2 3 0 1
Naive Approach: This approach is already discussed here. But the complexity of this approach is O(N2).
Efficient Approach:
- We can say that if number A divides a number B then A is a factor of B. So, we need to find the number of previous elements whose factor is the current element.
- We will maintain a count array that contains the count of the factor of each element.
- Now, Iterate over the array, and for each element
- Make the answer of the current element equal to count [ arr[i] ] and
- Increment the frequency of each factor of arr[i] in the count array.
- Make the answer of the current element equal to count [ arr[i] ] and
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Utility function to print the// elements of the arrayvoid printArr(int arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Function to increment the count// for each factor of given valvoid IncrementFactors(int count[], int val){ for (int i = 1; i * i <= val; i++) { if (val % i == 0) { if (i == val / i) { count[i]++; } else { count[i]++; count[val / i]++; } } }}// Function to generate and print// the required arrayvoid generateArr(int A[], int n){ int B[n]; // Find max element of array int maxi = *max_element(A, A + n); // Create count array of maxi size int count[maxi + 1] = { 0 }; // For every element of the array for (int i = 0; i < n; i++) { // Count[ A[i] ] denotes how many // previous elements are there whose // factor is the current element. B[i] = count[A[i]]; // Increment in count array for // factors of A[i] IncrementFactors(count, A[i]); } // Print the generated array printArr(B, n);}// Driver codeint main(){ int arr[] = { 8, 1, 28, 4, 2, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); generateArr(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Utility function to print the// elements of the arraystatic void printArr(int arr[], int n){ for(int i = 0; i < n; i++) System.out.print(arr[i] + " ");}// Function to increment the count// for each factor of given valstatic void IncrementFactors(int count[], int val){ for(int i = 1; i * i <= val; i++) { if (val % i == 0) { if (i == val / i) { count[i]++; } else { count[i]++; count[val / i]++; } } }}// Function to generate and print// the required arraystatic void generateArr(int A[], int n){ int []B = new int[n]; // Find max element of array int maxi = Arrays.stream(A).max().getAsInt(); // Create count array of maxi size int count[] = new int[maxi + 1]; // For every element of the array for(int i = 0; i < n; i++) { // Count[ A[i] ] denotes how many // previous elements are there whose // factor is the current element. B[i] = count[A[i]]; // Increment in count array for // factors of A[i] IncrementFactors(count, A[i]); } // Print the generated array printArr(B, n);}// Driver codepublic static void main(String[] args){ int arr[] = { 8, 1, 28, 4, 2, 6, 7 }; int n = arr.length; generateArr(arr, n);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 implementation of the approach # Utility function to print# elements of the arraydef printArr(arr, n): for i in range(n): print(arr[i], end = " ")# Function to increment the count# for each factor of given valdef IncrementFactors(count, val): i = 1 while(i * i <= val): if (val % i == 0): if (i == val // i): count[i] += 1 else: count[i] += 1 count[val // i] += 1 i += 1# Function to generate and print# the required arraydef generateArr(A, n): B = [0] * n # Find max element of arr maxi = max(A) # Create count array of maxi size count = [0] * (maxi + 1) # For every element of the array for i in range(n): # Count[ A[i] ] denotes how many # previous elements are there whose # factor is the current element. B[i] = count[A[i]] # Increment in count array for # factors of A[i] IncrementFactors(count, A[i]) # Print the generated array printArr(B, n)# Driver codearr = [ 8, 1, 28, 4, 2, 6, 7 ]n = len(arr)generateArr(arr, n)# This code is contributed by code_hunt |
C#
// C# implementation of the approachusing System;using System.Linq;class GFG{// Utility function to print the// elements of the arraystatic void printArr(int []arr, int n){ for(int i = 0; i < n; i++) Console.Write(arr[i] + " ");}// Function to increment the count// for each factor of given valstatic void IncrementFactors(int []count, int val){ for(int i = 1; i * i <= val; i++) { if (val % i == 0) { if (i == val / i) { count[i]++; } else { count[i]++; count[val / i]++; } } }}// Function to generate and print// the required arraystatic void generateArr(int []A, int n){ int []B = new int[n]; // Find max element of array int maxi = A.Max(); // Create count array of maxi size int []count = new int[maxi + 1]; // For every element of the array for(int i = 0; i < n; i++) { // Count[ A[i] ] denotes how many // previous elements are there whose // factor is the current element. B[i] = count[A[i]]; // Increment in count array for // factors of A[i] IncrementFactors(count, A[i]); } // Print the generated array printArr(B, n);}// Driver codepublic static void Main(String[] args){ int []arr = { 8, 1, 28, 4, 2, 6, 7 }; int n = arr.Length; generateArr(arr, n);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript implementation of the approach// Utility function to print the// elements of the arrayfunction printArr(arr, n){ for (let i = 0; i < n; i++) document.write(arr[i] + " ");}// Function to increment the count// for each factor of given valfunction IncrementFactors(count, val){ for (let i = 1; i * i <= val; i++) { if (val % i == 0) { if (i == parseInt(val / i)) { count[i]++; } else { count[i]++; count[parseInt(val / i)]++; } } }}// Function to generate and print// the required arrayfunction generateArr(A, n){ let B = new Array(n); // Find max element of array let maxi = Math.max(...A); // Create count array of maxi size let count = new Array(maxi + 1).fill(0); // For every element of the array for (let i = 0; i < n; i++) { // Count[ A[i] ] denotes how many // previous elements are there whose // factor is the current element. B[i] = count[A[i]]; // Increment in count array for // factors of A[i] IncrementFactors(count, A[i]); } // Print the generated array printArr(B, n);}// Driver code let arr = [ 8, 1, 28, 4, 2, 6, 7 ]; let n = arr.length; generateArr(arr, n);</script> |
Output:
0 1 0 2 3 0 1
Time Complexity: O(N * sqrt(MaxElement))
Auxiliary Space: O(N), since there is an extra array involved thus it takes O(N) extra space , where N is the length of the 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!
Share your thoughts in the comments
