Dada una array arr[] y un entero K , la tarea es encontrar el elemento de la array a partir de índices no divisibles por K cuyo producto de dígitos sea un número compuesto .
Ejemplos:
Entrada: arr[] = {233, 144, 89, 71, 13, 21, 11, 34, 55, 23}, K = 3
Salida: 89
Explicación:
Los siguientes elementos tienen producto de dígitos como un número compuesto :
arr[0 ] = 233 : Producto de dígitos = 2 * 3 * 3 = 18
arr[1] = 144 : Producto de dígitos = 1 * 4 * 4 = 16
arr[2] = 89 : Producto de dígitos = 8 * 9 = 72
arr [7] = 34 : Producto de dígitos = 3 * 4 = 12
arr[8] = 55 : Producto de dígitos = 5 * 5 = 25
Por lo tanto, el producto compuesto más grande de dígitos de elementos de array en índices no divisibles por K ( = 3) es 72 .Entrada: arr[] = {122, 566, 131, 211, 721, 19, 65, 1111, 111777}, K = 4
Salida: 566
Enfoque: siga los pasos que se indican a continuación para resolver el problema
- Recorre la array dada arr[] .
- Para cada elemento del arreglo , verifique si el producto de sus dígitos es un compuesto o si el producto de sus dígitos es menor o igual a 1 .
- Si el producto de sus dígitos es compuesto y su posición es divisible por k entonces
- Inserte el elemento en ans variable y su Composite DigitProduct en el vector pq .
- Finalmente, busque el elemento con el producto de dígitos compuesto más grande después de ordenar los elementos en el vector pq .
A continuación se muestra la implementación del enfoque anterior:
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 not
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 number
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 not
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 array
int 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 Code
int 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 approach
import 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 not
static 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 number
static 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 not
static 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 array
static 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 Code
public 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 approach from math import ceil, sqrt # Function to check if a number # is a composite number or not def 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 number def 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 not def 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 array def 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 Code if __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 approach
using 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 not
static 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 number
static 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 not
static 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 array
static 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 Code
public 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 approach
class pair
{
constructor(first,second)
{
this.first = first;
this.second = second;
}
}
// Function to check if a number
// is a composite number or not
function 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 number
function 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 not
function 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 array
function 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 Code
let 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>
Producción:
89
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por crisscross y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA