Dada una array arr[] que consta de enteros no negativos, la tarea es imprimir la longitud de la subsecuencia más larga de la array dada cuya suma de dígitos de cada elemento es un número compuesto .
Ejemplos:
Entrada: arr[] = {13, 55, 7, 3, 5, 21, 233, 144, 89}
Salida: 4
Explicación: Los siguientes elementos de la array tienen una suma de dígitos igual a un número compuesto:
- 13 -> 1 + 3 = 4
- 55 -> 5 + 5 = 10
- 233 -> 2 + 3 + 3 = 8
- 144 -> 1 + 4 + 4 = 9
Por lo tanto, la subsecuencia más larga requerida es {13, 55, 233, 144} de longitud 4.
Entrada: arr[] = {34, 13, 11, 8, 3, 55, 23}
Salida: 3
Explicación: Los siguientes elementos de la array tienen una suma de dígitos igual a un número compuesto:
- 13 -> 1 + 3 = 4
- 8 -> 8 = 8
- 55 -> 5 + 5 = 10
Por lo tanto, la subsecuencia más larga requerida es {13, 8, 55} de longitud 3.
Enfoque: siga los pasos que se indican a continuación para resolver el problema:
- Recorre la array dada .
- Para cada elemento de la array, compruebe si la suma de sus dígitos es primo o si la suma de sus dígitos es igual a 1 .
- Si la suma de sus dígitos es primo, continúe con el siguiente elemento de la array. De lo contrario, aumente la longitud de la subsecuencia requerida en 1 .
- Finalmente, después de completar el recorrido de la array, imprima la longitud de la subsecuencia obtenida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// Function to generate prime numbers
// using Sieve of Eratosthenes
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 find the digit sum
// of a given number
int digitSum(int number)
{
// Stores the sum of digits
int sum = 0;
while (number > 0) {
// Extract digits and
// add to the sum
sum += (number % 10);
number /= 10;
}
// Return the sum
// of the digits
return sum;
}
// Function to find the longest subsequence
// with sum of digits of each element equal
// to a composite number
void longestCompositeDigitSumSubsequence(
int arr[], int n)
{
int count = 0;
bool prime[N + 1];
memset(prime, true, sizeof(prime));
SieveOfEratosthenes(prime, N);
for (int i = 0; i < n; i++) {
// Calculate sum of digits
// of current array element
int res = digitSum(arr[i]);
// If sum of digits
// equal to 1
if (res == 1) {
continue;
}
// If sum of digits is
// a prime
if (!prime[res]) {
count++;
}
}
cout << count << endl;
}
// Driver Code
int main()
{
int arr[] = { 13, 55, 7, 3, 5, 1,
10, 21, 233, 144, 89 };
int n = sizeof(arr)
/ sizeof(arr[0]);
// Function call
longestCompositeDigitSumSubsequence(
arr, n);
return 0;
}
Java
// Java implementation of the
// above approach
import java.util.*;
class GFG{
static int N = 100005;
// Function to generate prime numbers
// using Sieve of Eratosthenes
static 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 find the digit sum
// of a given number
static int digitSum(int number)
{
// Stores the sum of digits
int sum = 0;
while (number > 0)
{
// Extract digits and
// add to the sum
sum += (number % 10);
number /= 10;
}
// Return the sum
// of the digits
return sum;
}
// Function to find the longest subsequence
// with sum of digits of each element equal
// to a composite number
static void longestCompositeDigitSumSubsequence(int []arr,
int n)
{
int count = 0;
boolean []prime = new boolean[N + 1];
for(int i = 0; i <= N; i++)
prime[i] = true;
SieveOfEratosthenes(prime, N);
for(int i = 0; i < n; i++)
{
// Calculate sum of digits
// of current array element
int res = digitSum(arr[i]);
// If sum of digits
// equal to 1
if (res == 1)
{
continue;
}
// If sum of digits is
// a prime
if (prime[res] == false)
{
count++;
}
}
System.out.println(count);
}
// Driver Code
public static void main(String[] args)
{
int []arr = { 13, 55, 7, 3, 5, 1,
10, 21, 233, 144, 89 };
int n = arr.length;
// Function call
longestCompositeDigitSumSubsequence(arr, n);
}
}
// This code is contributed by Stream_Cipher
Python3
# Python3 implementation of the # above approach N = 100005 # Function to generate prime numbers # using Sieve of Eratosthenes def SieveOfEratosthenes(prime, p_size): # Set 0 and 1 as non-prime prime[0] = False prime[1] = False p = 2 while p * p <= p_size: # 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 p += 1 # Function to find # the digit sum of # a given number def digitSum(number): # Stores the sum # of digits sum = 0 while (number > 0): # Extract digits and # add to the sum sum += (number % 10) number //= 10 # Return the sum # of the digits return sum # Function to find the longest subsequence # with sum of digits of each element equal # to a composite number def longestCompositeDigitSumSubsequence(arr, n): count = 0 prime = [True] * (N + 1) SieveOfEratosthenes(prime, N) for i in range(n): # Calculate sum of digits # of current array element res = digitSum(arr[i]) # If sum of digits # equal to 1 if (res == 1): continue # If sum of digits is # a prime if (not prime[res]): count += 1 print (count) # Driver Code if __name__ == "__main__": arr = [13, 55, 7, 3, 5, 1, 10, 21, 233, 144, 89] n = len(arr) # Function call longestCompositeDigitSumSubsequence(arr, n) # This code is contributed by Chitranayal
C#
// C# implementation of the
// above approach
using System.Collections.Generic;
using System;
class GFG{
static int N = 100005;
// Function to generate prime numbers
// using Sieve of Eratosthenes
static 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 find the digit sum
// of a given number
static int digitSum(int number)
{
// Stores the sum of digits
int sum = 0;
while (number > 0)
{
// Extract digits and
// add to the sum
sum += (number % 10);
number /= 10;
}
// Return the sum
// of the digits
return sum;
}
// Function to find the longest subsequence
// with sum of digits of each element equal
// to a composite number
static void longestCompositeDigitSumSubsequence(int []arr,
int n)
{
int count = 0;
bool []prime = new bool[N + 1];
for(int i = 0; i <= N; i++)
prime[i] = true;
SieveOfEratosthenes(prime, N);
for(int i = 0; i < n; i++)
{
// Calculate sum of digits
// of current array element
int res = digitSum(arr[i]);
// If sum of digits
// equal to 1
if (res == 1)
{
continue;
}
// If sum of digits is
// a prime
if (prime[res] == false)
{
count++;
}
}
Console.WriteLine(count);
}
// Driver Code
public static void Main()
{
int []arr = { 13, 55, 7, 3, 5, 1,
10, 21, 233, 144, 89 };
int n = arr.Length;
// Function call
longestCompositeDigitSumSubsequence(arr, n);
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript implementation of the
// above approach
let N = 100005;
// Function to generate prime numbers
// using Sieve of Eratosthenes
function SieveOfEratosthenes(prime,p_size)
{
// Set 0 and 1 as non-prime
prime[0] = false;
prime[1] = false;
for(let p = 2; p * p <= p_size; p++)
{
// If p is a prime
if (prime[p])
{
// Set all multiples of p as non-prime
for(let i = p * 2; i <= p_size; i += p)
prime[i] = false;
}
}
}
// Function to find the digit sum
// of a given number
function digitSum(number)
{
// Stores the sum of digits
let sum = 0;
while (number > 0)
{
// Extract digits and
// add to the sum
sum += (number % 10);
number =Math.floor(number/ 10);
}
// Return the sum
// of the digits
return sum;
}
// Function to find the longest subsequence
// with sum of digits of each element equal
// to a composite number
function longestCompositeDigitSumSubsequence(arr,n)
{
let count = 0;
let prime = new Array(N + 1);
for(let i = 0; i <= N; i++)
prime[i] = true;
SieveOfEratosthenes(prime, N);
for(let i = 0; i < n; i++)
{
// Calculate sum of digits
// of current array element
let res = digitSum(arr[i]);
// If sum of digits
// equal to 1
if (res == 1)
{
continue;
}
// If sum of digits is
// a prime
if (prime[res] == false)
{
count++;
}
}
document.write(count);
}
// Driver Code
let arr=[13, 55, 7, 3, 5, 1,
10, 21, 233, 144, 89 ];
let n = arr.length;
// Function call
longestCompositeDigitSumSubsequence(arr, n);
// This code is contributed by rag2127
</script>
Producción:
4
Complejidad de tiempo : O(N)
Espacio auxiliar: O(log 10 (maxm)), donde maxm es el elemento de array maxm
Publicación traducida automáticamente
Artículo escrito por crisscross y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA