Length of longest subsequence having sum of digits of each element as a Composite Number
Given an array arr[] consisting of non-negative integers, the task is to print the length of the longest subsequence from the given array whose sum of digits of each element is a composite numbers.
Examples:
Input: arr[] = {13, 55, 7, 3, 5, 21, 233, 144, 89}
Output: 4
Explanation: Following array elements have sum of digits equal to a composite number:
- 13 -> 1 + 3 = 4
- 55 -> 5 + 5 = 10
- 233 -> 2 + 3 + 3 = 8
- 144 -> 1 + 4 + 4 = 9
Therefore, the required the longest subsequence is {13, 55, 233, 144} of length 4.
Input: arr[] = {34, 13, 11, 8, 3, 55, 23}
Output: 3
Explanation: Following array elements have sum of digits equal to a composite number:
- 13 -> 1 + 3 = 4
- 8 -> 8 = 8
- 55 -> 5 + 5 = 10
Therefore, the required the longest subsequence is {13, 8, 55} of length 3.
Approach: Follow the steps given below to solve the problem:
- Traverse the given array.
- For each array element, check if the sum of its digits is prime or the sum of its digits is equal to 1.
- If sum of its digits is prime, then proceed to the next array element. Otherwise, increase the length of the required subsequence by 1.
- Finally, after complete traversal of the array, print the length of The subsequence obtained.
Below is the implementation of the above approach:
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> |
4
Time Complexity: O(N)
Auxiliary Space: O(log10(maxm)), where maxm is the maxm array element