Given an array arr[], the task is to determine the number of elements of the array which are not divisible by any other element in the given array.
Examples:
Input: arr[] = {86, 45, 18, 4, 8, 28, 19, 33, 2}
Output: 4
Explanation:
The elements are {2, 19, 33, 45} are not divisible by any other array element.Input: arr[] = {3, 3, 3}
Output: 0
Naive Approach: The naive approach is to iterate over the entire array and count the number of elements that are not divisible by any other elements in the given array and print the count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define ll long long intusing namespace std;// Function to count the number of// elements of array which are not// divisible by any other element// in the array arr[]int count(int a[], int n){ int countElements = 0; // Iterate over the array for (int i = 0; i < n; i++) { bool flag = true; for (int j = 0; j < n; j++) { // Check if the element // is itself or not if (i == j) continue; // Check for divisibility if (a[i] % a[j] == 0) { flag = false; break; } } if (flag == true) ++countElements; } // Return the final result return countElements;}// Driver Codeint main(){ // Given array int arr[] = { 86, 45, 18, 4, 8, 28, 19, 33, 2 }; int n = sizeof(arr) / sizeof(int); // Function Call cout << count(arr, n); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to count the number of// elements of array which are not// divisible by any other element// in the array arr[]static int count(int a[], int n){ int countElements = 0; // Iterate over the array for(int i = 0; i < n; i++) { boolean flag = true; for(int j = 0; j < n; j++) { // Check if the element // is itself or not if (i == j) continue; // Check for divisibility if (a[i] % a[j] == 0) { flag = false; break; } } if (flag == true) ++countElements; } // Return the final result return countElements;}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = { 86, 45, 18, 4, 8, 28, 19, 33, 2 }; int n = arr.length; // Function call System.out.print(count(arr, n));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for # the above approach# Function to count the number of# elements of array which are not# divisible by any other element# in the array arr[]def count(a, n): countElements = 0 # Iterate over the array for i in range (n): flag = True for j in range (n): # Check if the element # is itself or not if (i == j): continue # Check for divisibility if (a[i] % a[j] == 0): flag = False break if (flag == True): countElements += 1 # Return the final result return countElements# Driver Codeif __name__ == "__main__": # Given array arr = [86, 45, 18, 4, 8, 28, 19, 33, 2] n = len(arr) # Function Call print( count(arr, n))# This code is contributed by Chitranayal |
C#
// C# program for the // above approachusing System;class GFG{// Function to count the // number of elements of // array which are not// divisible by any other // element in the array []arrstatic int count(int []a, int n){ int countElements = 0; // Iterate over the array for(int i = 0; i < n; i++) { bool flag = true; for(int j = 0; j < n; j++) { // Check if the element // is itself or not if (i == j) continue; // Check for divisibility if (a[i] % a[j] == 0) { flag = false; break; } } if (flag == true) ++countElements; } // Return the readonly result return countElements;}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = {86, 45, 18, 4, 8, 28, 19, 33, 2}; int n = arr.Length; // Function call Console.Write(count(arr, n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Function to count the number of// elements of array which are not// divisible by any other element// in the array arr[]function count(a, n){ let countElements = 0; // Iterate over the array for (let i = 0; i < n; i++) { let flag = true; for (let j = 0; j < n; j++) { // Check if the element // is itself or not if (i == j) continue; // Check for divisibility if (a[i] % a[j] == 0) { flag = false; break; } } if (flag == true) ++countElements; } // Return the final result return countElements;}// Driver Code // Given array let arr = [ 86, 45, 18, 4, 8, 28, 19, 33, 2 ]; let n = arr.length; // Function Call document.write(count(arr, n));</script> |
Output
4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, we will use the concept of Sieve of Eratosthenes. Below are the steps:
- Initialize a boolean array(say v[]) of size equal to the maximum element present in the array + 1 with true at every index.
- Traverse the given array arr[] and change the value at the index of multiple of current elements as false in the array v[].
- Create a Hashmap and store the frequency of each element in it.
- For each element(say current_element) in the array, if v[current_element] is true then that element is not divisible by any other element in the given array and increment the count for the current element.
- Print the final value of count after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// elements of array which are not// divisible by any other element// of same arrayint countEle(int a[], int n){ // Length for boolean array int len = 0; // Hash map for storing the // element and it's frequency unordered_map<int, int> hmap; for (int i = 0; i < n; i++) { // Update the maximum element len = max(len, a[i]); hmap[a[i]]++; } // Boolean array of size // of the max element + 1 bool v[len + 1]; for (int i = 0; i <= len; i++) { v[i] = true; } // Marking the multiples as false for (int i = 0; i < n; i++) { if (v[a[i]] == false) continue; for (int j = 2 * a[i]; j <= len; j += a[i]) { v[j] = false; } } // To store the final count int count = 0; // Traverse boolean array for (int i = 1; i <= len; i++) { // Check if i is not divisible by // any other array elements and // appears in the array only once if (v[i] == true && hmap.count(i) == 1 && hmap[i] == 1) { count += 1; } } // Return the final Count return count;}// Driver Codeint main(){ // Given array int arr[] = { 86, 45, 18, 4, 8, 28, 19, 33, 2 }; int n = sizeof(arr) / sizeof(int); // Function Call cout << countEle(arr, n); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{// Function to count the // number of elements of // array which are not // divisible by any other // element of same arraystatic int countEle(int a[], int n){ // Length for boolean array int len = 0; // Hash map for storing the // element and it's frequency HashMap<Integer, Integer> hmap = new HashMap<>(); for (int i = 0; i < n; i++) { // Update the maximum element len = Math.max(len, a[i]); if(hmap.containsKey(a[i])) { hmap.put(a[i], hmap.get(a[i]) + 1); } else { hmap.put(a[i], 1); } } // Boolean array of size // of the max element + 1 boolean []v = new boolean[len + 1]; for (int i = 0; i <= len; i++) { v[i] = true; } // Marking the multiples // as false for (int i = 0; i < n; i++) { if (v[a[i]] == false) continue; for (int j = 2 * a[i]; j <= len; j += a[i]) { v[j] = false; } } // To store the // final count int count = 0; // Traverse boolean array for (int i = 1; i <= len; i++) { // Check if i is not divisible by // any other array elements and // appears in the array only once if (v[i] == true && hmap.containsKey(i) && hmap.get(i) == 1 && hmap.get(i) == 1) { count += 1; } } // Return the final // Count return count;}// Driver Codepublic static void main(String[] args){ // Given array int arr[] = {86, 45, 18, 4, 8, 28, 19, 33, 2}; int n = arr.length; // Function Call System.out.print(countEle(arr, n));}}// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approach# Function to count the number of# elements of array which are not# divisible by any other element# of same arraydef countEle(a, n): # Length for boolean array len = 0 # Hash map for storing the # element and it's frequency hmap = {} for i in range(n): # Update the maximum element len = max(len, a[i]) hmap[a[i]] = hmap.get(a[i], 0) + 1 # Boolean array of size # of the max element + 1 v = [True for i in range(len + 1)] # Marking the multiples as false for i in range(n): if (v[a[i]] == False): continue for j in range(2 * a[i], len + 1, a[i]): v[j] = False # To store the final count count = 0 # Traverse boolean array for i in range(1, len + 1): # Check if i is not divisible by # any other array elements and # appears in the array only once if (v[i] == True and (i in hmap) and hmap[i] == 1): count += 1 # Return the final Count return count# Driver Codeif __name__ == '__main__': # Given array arr = [86, 45, 18, 4, 8, 28, 19, 33, 2] n = len(arr) # Function Call print(countEle(arr, n)) # This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;using System.Collections.Generic;class GFG{// Function to count the // number of elements of // array which are not // divisible by any other // element of same arraystatic int countEle(int []a, int n){ // Length for bool array int len = 0; // Hash map for storing the // element and it's frequency Dictionary<int, int> hmap = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { // Update the maximum // element len = Math.Max(len, a[i]); if(hmap.ContainsKey(a[i])) { hmap[a[i]]++; } else { hmap.Add(a[i], 1); } } // Boolean array of size // of the max element + 1 bool []v = new bool[len + 1]; for (int i = 0; i <= len; i++) { v[i] = true; } // Marking the multiples // as false for (int i = 0; i < n; i++) { if (v[a[i]] == false) continue; for (int j = 2 * a[i]; j <= len; j += a[i]) { v[j] = false; } } // To store the // readonly count int count = 0; // Traverse bool array for (int i = 1; i <= len; i++) { // Check if i is not divisible by // any other array elements and // appears in the array only once if (v[i] == true && hmap.ContainsKey(i) && hmap[i] == 1 && hmap[i] == 1) { count += 1; } } // Return the readonly // Count return count;}// Driver Codepublic static void Main(String[] args){ // Given array int []arr = {86, 45, 18, 4, 8, 28, 19, 33, 2}; int n = arr.Length; // Function Call Console.Write(countEle(arr, n));}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for// the above approach// Function to count the// number of elements of// array which are not// divisible by any other// element of same arrayfunction countEle(a, n){ // Length for boolean array let len = 0; // Hash map for storing the // element and it's frequency let hmap = new Map(); for (let i = 0; i < n; i++) { // Update the maximum element len = Math.max(len, a[i]); if(hmap.has(a[i])) { hmap.set(a[i], hmap.get(a[i]) + 1); } else { hmap.set(a[i], 1); } } // Boolean array of size // of the max element + 1 let v = Array.from({length: len + 1}, (_, i) => 0); for (let i = 0; i <= len; i++) { v[i] = true; } // Marking the multiples // as false for (let i = 0; i < n; i++) { if (v[a[i]] == false) continue; for (let j = 2 * a[i]; j <= len; j += a[i]) { v[j] = false; } } // To store the // final count let count = 0; // Traverse boolean array for (let i = 1; i <= len; i++) { // Check if i is not divisible by // any other array elements and // appears in the array only once if (v[i] == true && hmap.has(i) && hmap.get(i) == 1 && hmap.get(i) == 1) { count += 1; } } // Return the final // Count return count;}// Driver code // Given array let arr = [86, 45, 18, 4, 8, 28, 19, 33, 2]; let n = arr.length; // Function Call document.write(countEle(arr, n)); // This code is contributed by souravghosh0416.</script> |
Output
4
Time Complexity: O(N*log(M)) where N is the number of elements in the given array and M is the maximum element in the given array.
Auxiliary Space: O(M + N) where N is the number of elements in the given array and M is the maximum element in 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!
