Given an array arr[] consisting of N non-negative integers, the task is to count the number of array elements whose product of digits is a composite number.
Examples:
Input: arr[] = {13, 55, 7, 13, 11, 71, 233, 144, 89}
Output: 4
Explanation: The array elements having product of digits equal to a composite number are 55 (5 * 5 = 25), 233 (2 * 3 * 3 = 18), 144 (1 * 4 * 4 = 16), 89 ( = 8 * 9 = 72)Input: arr[] = {34, 13, 55, 11, 8, 3, 55, 23}
Output: 3
Explanation: The array elements having product of digits equal to a composite number are 34 ( = 3 * 4 = 12), 55 ( 5 * 5 = 25), 23 ( = 2 * 3 = 6)
Approach: Follow the steps below to solve the problem:
- Precompute and store all the prime numbers using sieve of Eratosthenes.
- Create a Set to store all the distinct array elements whose product of digits is a composite number.
- Traverse the given array and for each array element, check if the product of all its digits is prime number or not. If found to be true, add the current element to the Set.
- Otherwise, proceed to the next array element.
- After traversing, print the size of the set as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#include <set>using namespace std;#define N 100005// Function to generate prime numbers// using Sieve of Eratosthenesvoid SieveOfEratosthenes(bool prime[], int p_size){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for (int p = 2; p * p <= p_size; p++) { // If p is a prime if (prime[p]) { // Set all multiples of p as non-prime for (int i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to calculate the product// of digits of the given numberlong long int digitProduct(int number){ // Stores the product of digits long long int res = 1; while (number > 0) { // Extract digits and // add to the sum res *= (number % 10); number /= 10; } // Return the product // of its digits return res;}// Function to print number of distinct// values with digit product as compositevoid DistinctCompositeDigitProduct(int arr[], int n){ // Initialize set set<int> output; // Initialize boolean array bool prime[N + 1]; memset(prime, true, sizeof(prime)); // Pre-compute primes SieveOfEratosthenes(prime, N); // Traverse array for (int i = 0; i < n; i++) { // Stores the product of digits // of the current array element long long int ans = digitProduct(arr[i]); // If Product of digits is // less than or equal to 1 if (ans <= 1) { continue; } // If Product of digits is // not a prime if (!prime[ans]) { output.insert(ans); } } // Print the answer cout << output.size() << endl;}// Driver Codeint main(){ // Given array int arr[] = { 13, 55, 7, 13, 11, 71, 233, 233, 144, 89 }; // Given size int n = sizeof(arr) / sizeof(arr[0]); // Function call DistinctCompositeDigitProduct(arr, n); return 0;} |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ static int N = 100005; // Function to generate prime numbers// using Sieve of Eratosthenesstatic void SieveOfEratosthenes(boolean prime[], int p_size){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for(int p = 2; p * p <= p_size; p++) { // If p is a prime if (prime[p]) { // Set all multiples of p as non-prime for(int i = p * 2; i <= p_size; i += p) prime[i] = false; } }} // Function to calculate the product// of digits of the given numberstatic int digitProduct(int number){ // Stores the product of digits int res = 1; while (number > 0) { // Extract digits and // add to the sum res *= (number % 10); number /= 10; } // Return the product // of its digits return res;} // Function to print number of distinct// values with digit product as compositestatic void DistinctCompositeDigitProduct(int arr[], int n){ // Initialize set TreeSet<Integer> output = new TreeSet<Integer>(); // Initialize boolean array boolean prime[] = new boolean[N + 1]; Arrays.fill(prime, true); // Pre-compute primes SieveOfEratosthenes(prime, N); // Traverse array for(int i = 0; i < n; i++) { // Stores the product of digits // of the current array element int ans = digitProduct(arr[i]); // If Product of digits is // less than or equal to 1 if (ans <= 1) { continue; } // If Product of digits is // not a prime if (!prime[ans]) { output.add(ans); } } // Print the answer System.out.print(output.size());} // Driver Code public static void main(String[] args) { // Given array int arr[] = { 13, 55, 7, 13, 11, 71, 233, 233, 144, 89 }; // Given size int n = arr.length; // Function call DistinctCompositeDigitProduct(arr, n);} } // This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approachN = 100005from math import sqrt# Function to generate prime numbers# using Sieve of Eratosthenesdef SieveOfEratosthenes(prime, p_size): # Set 0 and 1 as non-prime prime[0] = False prime[1] = False for p in range(2, int(sqrt(p_size)), 1): # If p is a prime if (prime[p]): # Set all multiples of p as non-prime for i in range(p * 2, p_size + 1, p): prime[i] = False# Function to calculate the product# of digits of the given numberdef digitProduct(number): # Stores the product of digits res = 1 while(number > 0): # Extract digits and # add to the sum res *= (number % 10) number //= 10 # Return the product # of its digits return res# Function to print number of distinct# values with digit product as compositedef DistinctCompositeDigitProduct(arr, n): # Initialize set output = set() # Initialize boolean array prime = [True for i in range(N + 1)] # Pre-compute primes SieveOfEratosthenes(prime, N) # Traverse array for i in range(n): # of the current array element ans = digitProduct(arr[i]) # If Product of digits is # less than or equal to 1 if (ans <= 1): continue # If Product of digits is # not a prime if (prime[ans] == False): output.add(ans) # Print the answer print(len(output))# Driver Codeif __name__ == '__main__': # Given array arr = [13, 55, 7, 13, 11, 71, 233, 233, 144, 89] # Given size n = len(arr) # Function call DistinctCompositeDigitProduct(arr, n) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System;using System.Collections.Generic; class GFG{ static int N = 100005; // Function to generate prime numbers// using Sieve of Eratosthenesstatic void SieveOfEratosthenes(bool[] prime, int p_size){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for(int p = 2; p * p <= p_size; p++) { // If p is a prime if (prime[p]) { // Set all multiples of p as non-prime for(int i = p * 2; i <= p_size; i += p) prime[i] = false; } }} // Function to calculate the product// of digits of the given numberstatic int digitProduct(int number){ // Stores the product of digits int res = 1; while (number > 0) { // Extract digits and // add to the sum res *= (number % 10); number /= 10; } // Return the product // of its digits return res;} // Function to print number of distinct// values with digit product as compositestatic void DistinctCompositeDigitProduct(int[] arr, int n){ // Initialize set SortedSet<int> output = new SortedSet<int>(); // Initialize boolean array bool[] prime = new bool[N + 1]; for(int i = 0; i < N + 1; i++) { prime[i] = true; } // Pre-compute primes SieveOfEratosthenes(prime, N); // Traverse array for(int i = 0; i < n; i++) { // Stores the product of digits // of the current array element int ans = digitProduct(arr[i]); // If Product of digits is // less than or equal to 1 if (ans <= 1) { continue; } // If Product of digits is // not a prime if (!prime[ans]) { output.Add(ans); } } // Print the answer Console.WriteLine(output.Count);} // Driver Codepublic static void Main(){ // Given array int[] arr = { 13, 55, 7, 13, 11, 71, 233, 233, 144, 89 }; // Given size int n = arr.Length; // Function call DistinctCompositeDigitProduct(arr, n);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// javascript program for the above approachvar N = 100005;// Function to generate prime numbers// using Sieve of Eratosthenesfunction SieveOfEratosthenes(prime, p_size){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; var p,i; for (p = 2; p * p <= p_size; p++) { // If p is a prime if (prime[p]) { // Set all multiples of p as non-prime for (i = p * 2; i <= p_size; i += p) prime[i] = false; } }}// Function to calculate the product// of digits of the given numberfunction digitProduct(number){ // Stores the product of digits var res = 1; while (number > 0) { // Extract digits and // add to the sum res *= (number % 10); number = parseInt(number/10); } // Return the product // of its digits return res;}// Function to print number of distinct// values with digit product as compositefunction DistinctCompositeDigitProduct(arr, n){ // Initialize set var output = new Set(); // Initialize boolean array var prime = Array(N + 1).fill(true); // Pre-compute primes SieveOfEratosthenes(prime, N); var i; // Traverse array for (i = 0; i < n; i++) { // Stores the product of digits // of the current array element var ans = digitProduct(arr[i]); // If Product of digits is // less than or equal to 1 if (ans <= 1) { continue; } // If Product of digits is // not a prime if (prime[ans]==false) { output.add(ans); } } // Print the answer document.write(output.size);}// Driver Code // Given array var arr = [13, 55, 7, 13, 11, 71, 233, 233, 144, 89]; // Given size var n = arr.length; // Function call DistinctCompositeDigitProduct(arr, n); </script> |
Output:
4
Time Complexity: O(N + MlogM), where N is the size of the given array and M is the maximum array element.
Auxiliary Space: O(1)
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!
