Given an array arr[] of N positive integers, the task is to print the length of the longest subsequence of the array such that all of its elements are Nude Numbers.
Examples:
Input: arr[] = {34, 34, 2, 2, 3, 333, 221, 32 }
Output: 4
Explanation:
Longest Nude number subsequence is {2, 2, 3, 333} and hence the answer is 4.
Input: arr[] = {456, 44, 104, 133, 39, 325 }
Output: 1
Explanation:
Longest Nude number subsequence is {44} and hence the answer is 1.
Approach: To solve the problem follow the steps given below:
- Traverse the given array and for each element in the array and check if it is a Nude number or not.
- If the element is a Nude Number, it will be included in the resultant longest subsequence. Hence increment the count of elements in the subsequence by 1.
- Print the value of count after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h> using namespace std;// Function to check if the number// is a Nude numberbool isNudeNum(int n){ // Variable initialization int copy, length, flag = 0; copy = n; string temp; // Integer 'copy' is converted // to a string temp = to_string(copy); // Total digits in the number length = temp.length(); // Loop through all digits and check // if every digit divides n or not for (int i = 0; i < length; i++) { int num = temp[i] - '0'; if (num == 0 or n % num != 0) { // flag is used to keep check flag = 1; } } // Return true or false as per // the condition if (flag == 1) return false; else return true;}// Function to find the longest subsequence// which contain all Nude numbersint longestNudeSubseq(int arr[], int n){ int answer = 0; // Find the length of longest // Nude number subsequence for (int i = 0; i < n; i++) { if (isNudeNum(arr[i])) answer++; } return answer;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 34, 34, 2, 2, 3, 333, 221, 32 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << longestNudeSubseq(arr, n) << endl; return 0;} |
Java
// Java program for the above approachclass GFG{// Function to check if the number// is a Nude numberstatic boolean isNudeNum(int n){ // Variable initialization int copy, length, flag = 0; copy = n; String temp; // Integer 'copy' is converted // to a String temp = String.valueOf(copy); // Total digits in the number length = temp.length(); // Loop through all digits and check // if every digit divides n or not for(int i = 0; i < length; i++) { int num = temp.charAt(i) - '0'; if (num == 0 || n % num != 0) { // flag is used to keep check flag = 1; } } // Return true or false as per // the condition if (flag == 1) return false; else return true;}// Function to find the longest subsequence// which contain all Nude numbersstatic int longestNudeSubseq(int arr[], int n){ int answer = 0; // Find the length of longest // Nude number subsequence for(int i = 0; i < n; i++) { if (isNudeNum(arr[i])) answer++; } return answer;}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = { 34, 34, 2, 2, 3, 333, 221, 32 }; int n = arr.length; // Function call System.out.print(longestNudeSubseq(arr, n) + "\n");}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program for the above approach# Function to check if the number # is a Nude number def isNudeNum(n): # Variable initialization flag = 0 copy = n # Integer 'copy' is converted # to a string temp = str(copy) # Total digits in the number length = len(temp) # Loop through all digits and check # if every digit divides n or not for i in range(length): num = ord(temp[i]) - ord('0') if ((num == 0) or (n % num != 0)): # flag is used to keep check flag = 1 # Return true or false as per # the condition if (flag == 1): return False else: return True# Function to find the longest subsequence # which contain all Nude numbers def longestNudeSubseq(arr, n): answer = 0 # Find the length of longest # Nude number subsequence for i in range(n): if (isNudeNum(arr[i])): answer += 1 return answer # Driver Code # Given array arr[] arr = [ 34, 34, 2, 2, 3, 333, 221, 32 ] n = len(arr) # Function call print(longestNudeSubseq(arr, n))# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{// Function to check if the number// is a Nude numberstatic bool isNudeNum(int n){ // Variable initialization int copy, length, flag = 0; copy = n; String temp; // int 'copy' is converted // to a String temp = String.Join("", copy); // Total digits in the number length = temp.Length; // Loop through all digits and check // if every digit divides n or not for(int i = 0; i < length; i++) { int num = temp[i] - '0'; if (num == 0 || n % num != 0) { // flag is used to keep check flag = 1; } } // Return true or false as per // the condition if (flag == 1) return false; else return true;}// Function to find the longest subsequence// which contain all Nude numbersstatic int longestNudeSubseq(int []arr, int n){ int answer = 0; // Find the length of longest // Nude number subsequence for(int i = 0; i < n; i++) { if (isNudeNum(arr[i])) answer++; } return answer;}// Driver Codepublic static void Main(String[] args){ // Given array []arr int []arr = { 34, 34, 2, 2, 3, 333, 221, 32 }; int n = arr.Length; // Function call Console.Write(longestNudeSubseq(arr, n) + "\n");}}// This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript program for the above approach // Function to check if the number // is a Nude number function isNudeNum(n) { // Variable initialization let copy, length, flag = 0; copy = n; let temp; // Integer 'copy' is converted // to a string temp = copy.toString(); // Total digits in the number length = temp.length; // Loop through all digits and check // if every digit divides n or not for (let i = 0; i < length; i++) { let num = temp[i].charCodeAt() - '0'.charCodeAt(); if (num == 0 || n % num != 0) { // flag is used to keep check flag = 1; } } // Return true or false as per // the condition if (flag == 1) return false; else return true; } // Function to find the longest subsequence // which contain all Nude numbers function longestNudeSubseq(arr, n) { let answer = 0; // Find the length of longest // Nude number subsequence for (let i = 0; i < n; i++) { if (isNudeNum(arr[i])) answer++; } return answer; } // Given array arr[] let arr = [ 34, 34, 2, 2, 3, 333, 221, 32 ]; let n = arr.length; // Function Call document.write(longestNudeSubseq(arr, n)); // This code is contributed by divyesh072019.</script> |
Output:
4
Time Complexity: O(N*log10N)
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!
