Given an array arr[] and an integer K, the task is to find the array element from indices not divisible by K whose product of digits is a composite number.
Examples:
Input: arr[] = {233, 144, 89, 71, 13, 21, 11, 34, 55, 23}, K = 3
Output: 89
Explanation:
Following elements have product of digits as a composite number:
arr[0] = 233 : Product of digits = 2 * 3 * 3 = 18
arr[1] = 144 : Product of digits = 1 * 4 * 4 = 16
arr[2] = 89 : Product of digits = 8 * 9 = 72
arr[7] = 34 : Product of digits = 3 * 4 = 12
arr[8] = 55 : Product of digits = 5 * 5 = 25
Therefore, the largest composite product of digits of array elements at indices not divisible by K ( = 3) is 72.Input: arr[] = {122, 566, 131, 211, 721, 19, 65, 1111, 111777}, K = 4
Output: 566
Approach: Follow the steps given below to solve the problem
- Traverse the given array arr[].
- For each array element, check if the product of its digits is a composite or product of its digits is less than or equal to 1.
- If product of its digits is composite and its position is divisible by k then
- Insert the element in ans variable and its Composite DigitProduct in the vector pq.
- Finally, Find the element with the largest Composite DigitProduct after sorting the elements in the vector pq.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>#include <vector>using namespace std;// Function to check if a number// is a composite number or notbool isComposite(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if number is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check if number is a multiple // of any other prime number for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false;}// Function to calculate the product// of digits of a numberint digitProduct(int number){ // Stores the product of digits int product = 1; while (number > 0) { // Extract digits of a number product *= (number % 10); // Calculate product of digits number /= 10; } return product;}// Function to check if the product of digits// of a number is a composite number or notbool compositedigitProduct(int num){ // Stores product of digits int res = digitProduct(num); // If product of digits is equal to 1 if (res == 1) { return false; } // If product of digits is not prime if (isComposite(res)) { return true; } return false;}// Function to find the number with largest// composite product of digits from the indices// not divisible by k from the given arrayint largestCompositeDigitProduct(int a[], int n, int k){ vector<pair<int, int> > pq; // Traverse the array for (int i = 0; i < n; i++) { // If index is divisible by k if ((i % k) == 0) { continue; } // Check if product of digits // is a composite number or not if (compositedigitProduct(a[i])) { int b = digitProduct(a[i]); pq.push_back(make_pair(b, a[i])); } } // Sort the products sort(pq.begin(), pq.end()); return pq.back().second;}// Driver Codeint main(){ int arr[] = { 233, 144, 89, 71, 13, 21, 11, 34, 55, 23 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; int ans = largestCompositeDigitProduct( arr, n, k); cout << ans << endl; return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to check if a number// is a composite number or notstatic boolean isComposite(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if number is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check if number is a multiple // of any other prime number for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false;}// Function to calculate the product// of digits of a numberstatic int digitProduct(int number){ // Stores the product of digits int product = 1; while (number > 0) { // Extract digits of a number product *= (number % 10); // Calculate product of digits number /= 10; } return product;}// Function to check if the product of digits// of a number is a composite number or notstatic boolean compositedigitProduct(int num){ // Stores product of digits int res = digitProduct(num); // If product of digits is equal to 1 if (res == 1) { return false; } // If product of digits is not prime if (isComposite(res)) { return true; } return false;}// Function to find the number with largest// composite product of digits from the indices// not divisible by k from the given arraystatic int largestCompositeDigitProduct(int a[], int n, int k){ Vector<pair> pq = new Vector<pair>(); // Traverse the array for (int i = 0; i < n; i++) { // If index is divisible by k if ((i % k) == 0) { continue; } // Check if product of digits // is a composite number or not if (compositedigitProduct(a[i])) { int b = digitProduct(a[i]); pq.add(new pair(b, a[i])); } } // Sort the products Collections.sort(pq, (x, y) -> x.first - y.first); return pq.get(pq.size() - 1).second;}// Driver Codepublic static void main(String[] args){ int arr[] = { 233, 144, 89, 71, 13, 21, 11, 34, 55, 23 }; int n = arr.length; int k = 3; int ans = largestCompositeDigitProduct( arr, n, k); System.out.print(ans +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approachfrom math import ceil, sqrt# Function to check if a number# is a composite number or notdef isComposite(n): # Corner cases if (n <= 1): return False if (n <= 3): return False # Check if number is divisible by 2 or 3 if (n % 2 == 0 or n % 3 == 0): return True # Check if number is a multiple # of any other prime number for i in range(5, ceil(sqrt(n)),6): if (n % i == 0 or n % (i + 2) == 0): return True return False# Function to calculate the product# of digits of a numberdef digitProduct(number): # Stores the product of digits product = 1 while (number > 0): # Extract digits of a number product *= (number % 10) # Calculate product of digits number //= 10 return product# Function to check if the product of digits# of a number is a composite number or notdef compositedigitProduct(num): # Stores product of digits res = digitProduct(num) # If product of digits is equal to 1 if (res == 1): return False # If product of digits is not prime if (isComposite(res)): return True return False# Function to find the number with largest# composite product of digits from the indices# not divisible by k from the given arraydef largestCompositeDigitProduct(a, n, k): pq = [] # Traverse the array for i in range(n): # If index is divisible by k if ((i % k) == 0): continue # Check if product of digits # is a composite number or not if (compositedigitProduct(a[i])): b = digitProduct(a[i]) pq.append([b, a[i]]) # Sort the products pq = sorted (pq) return pq[-1][1]# Driver Codeif __name__ == '__main__': arr = [233, 144, 89, 71, 13, 21, 11, 34, 55, 23] n = len(arr) k = 3 ans = largestCompositeDigitProduct(arr, n, k) print (ans)# This code is contributed by divyesh072019 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{ class pair : IComparable<pair> { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } public int CompareTo(pair p) { return this.second-p.first; } } // Function to check if a number// is a composite number or notstatic bool isComposite(int n){ // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if number is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check if number is a multiple // of any other prime number for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false;}// Function to calculate the product// of digits of a numberstatic int digitProduct(int number){ // Stores the product of digits int product = 1; while (number > 0) { // Extract digits of a number product *= (number % 10); // Calculate product of digits number /= 10; } return product;}// Function to check if the product of digits// of a number is a composite number or notstatic bool compositedigitProduct(int num){ // Stores product of digits int res = digitProduct(num); // If product of digits is equal to 1 if (res == 1) { return false; } // If product of digits is not prime if (isComposite(res)) { return true; } return false;}// Function to find the number with largest// composite product of digits from the indices// not divisible by k from the given arraystatic int largestCompositeDigitProduct(int []a, int n, int k){ List<pair> pq = new List<pair>(); // Traverse the array for (int i = 0; i < n; i++) { // If index is divisible by k if ((i % k) == 0) { continue; } // Check if product of digits // is a composite number or not if (compositedigitProduct(a[i])) { int b = digitProduct(a[i]); pq.Add(new pair(b, a[i])); } } // Sort the products pq.Sort(); return pq[pq.Count - 1].second;}// Driver Codepublic static void Main(String[] args){ int []arr = { 233, 144, 89, 71, 13, 21, 11, 34, 55, 23 }; int n = arr.Length; int k = 3; int ans = largestCompositeDigitProduct( arr, n, k); Console.Write(ans +"\n");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to implement// the above approachclass pair{ constructor(first,second) { this.first = first; this.second = second; }}// Function to check if a number// is a composite number or notfunction isComposite(n){ // Corner cases if (n <= 1) return false; if (n <= 3) return false; // Check if number is divisible by 2 or 3 if (n % 2 == 0 || n % 3 == 0) return true; // Check if number is a multiple // of any other prime number for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return true; return false;}// Function to calculate the product// of digits of a numberfunction digitProduct(number){ // Stores the product of digits let product = 1; while (number > 0) { // Extract digits of a number product *= (number % 10); // Calculate product of digits number = Math.floor(number/10); } return product;}// Function to check if the product of digits// of a number is a composite number or notfunction compositedigitProduct(num){ // Stores product of digits let res = digitProduct(num); // If product of digits is equal to 1 if (res == 1) { return false; } // If product of digits is not prime if (isComposite(res)) { return true; } return false;}// Function to find the number with largest// composite product of digits from the indices// not divisible by k from the given arrayfunction largestCompositeDigitProduct(a,n,k){ let pq = []; // Traverse the array for (let i = 0; i < n; i++) { // If index is divisible by k if ((i % k) == 0) { continue; } // Check if product of digits // is a composite number or not if (compositedigitProduct(a[i])) { let b = digitProduct(a[i]); pq.push(new pair(b, a[i])); } } // Sort the products pq.sort(function(x, y) {return x.first - y.first}); return pq[pq.length-1].second;}// Driver Codelet arr=[233, 144, 89, 71, 13, 21, 11, 34, 55, 23];let n = arr.length;let k = 3;let ans = largestCompositeDigitProduct( arr, n, k);document.write(ans +"<br>");// This code is contributed by unknown2108</script> |
Output:
89
Time Complexity: O(N)
Auxiliary Space: O(N)
Share your thoughts in the comments
