Length of longest subsequence in an Array having all elements as Nude Numbers

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 number
bool 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 numbers
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 Code
int 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 approach
class GFG{

// Function to check if the number
// is a Nude number
static 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 numbers
static 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 Code
public 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
Python
# 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 approach
using System;

class GFG{

// Function to check if the number
// is a Nude number
static 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 numbers
static 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 Code
public 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
    // 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 
    console.log(longestNudeSubseq(arr, n));
    
    // This code is contributed by divyesh072019.

Output
4

Time Complexity: O(N*log10N)
Auxiliary Space: O(1)

Approach : Using Set or Hashing

To solve the problem follow the steps given below:

  • Firstly, create a set or hash table to store all Nude Numbers
  • Iterate over the given array and for each element check if it is a Nude Number
  • If it is then increment the count of Nude Numbers encountered.
  • After iterating through the array
  • The count of Nude Numbers encountered will give the length of the longest Nude Numbers subsequence.

Below is the implementation of the above approach:

C++
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

// Function to check if a number is a Nude Number
bool is_nude_number(int num)
{
    unordered_set<int> nude_numbers = { 2, 3, 5, 7 };

    // Check each digit of the number
    while (num > 0) {
        int digit = num % 10;
        // If the digit is not in the set of Nude Numbers,
        // return false
        if (nude_numbers.find(digit)
            == nude_numbers.end()) {
            return false;
        }
        num /= 10;
    }
    // If all digits are Nude Numbers, return true
    return true;
}

// Function to find the length of the longest subsequence of
// Nude Numbers
int longest_nude_numbers_subsequence(vector<int>& arr)
{
    int max_length
        = 0; // Initialize the maximum length to 0
    int current_length
        = 0; // Initialize the current length to 0

    // Iterate through the array
    for (int num : arr) {
        if (is_nude_number(num)) {
            // If the number is a Nude Number, increment the
            // current length
            current_length++;
            // Update the maximum length if needed
            max_length = max(max_length, current_length);
        }
        else {
            // If the number is not a Nude Number, reset the
            // current length
            current_length = 0;
        }
    }

    // Return the maximum length of the Nude Numbers
    // subsequence
    return max_length;
}

int main()
{
    vector<int> arr1 = { 34, 34, 2, 2, 3, 333, 221, 32 };
    // Find and print the length of the longest Nude Numbers
    // subsequence in arr1
    cout << longest_nude_numbers_subsequence(arr1) << endl;
    return 0;
}

// This code is contributed by Shivam Gupta
Java
import java.util.HashSet;

public class NudeNumbers {

    // Function to check if a number is a Nude Number
    static boolean isNudeNumber(int num)
    {
        HashSet<Integer> nudeNumbers = new HashSet<>();
        nudeNumbers.add(2);
        nudeNumbers.add(3);
        nudeNumbers.add(5);
        nudeNumbers.add(7);

        // Check each digit of the number
        while (num > 0) {
            int digit = num % 10;
            // If the digit is not in the set of Nude
            // Numbers, return false
            if (!nudeNumbers.contains(digit)) {
                return false;
            }
            num /= 10;
        }
        // If all digits are Nude Numbers, return true
        return true;
    }

    // Function to find the length of the longest
    // subsequence of Nude Numbers
    static int longestNudeNumbersSubsequence(int[] arr)
    {
        int maxLength
            = 0; // Initialize the maximum length to 0
        int currentLength
            = 0; // Initialize the current length to 0

        // Iterate through the array
        for (int num : arr) {
            if (isNudeNumber(num)) {
                // If the number is a Nude Number, increment
                // the current length
                currentLength++;
                // Update the maximum length if needed
                maxLength
                    = Math.max(maxLength, currentLength);
            }
            else {
                // If the number is not a Nude Number, reset
                // the current length
                currentLength = 0;
            }
        }

        // Return the maximum length of the Nude Numbers
        // subsequence
        return maxLength;
    }

    public static void main(String[] args)
    {
        int[] arr1 = { 34, 34, 2, 2, 3, 333, 221, 32 };
        // Find and print the length of the longest Nude
        // Numbers subsequence in arr1
        System.out.println(
            longestNudeNumbersSubsequence(arr1));
    }
}
Python
def is_nude_number(num):
    # Define a set of Nude Numbers
    nude_numbers = {2, 3, 5, 7}

    # Check if the number is a Nude Number
    while num > 0:
        digit = num % 10
        if digit not in nude_numbers:
            return False
        num //= 10
    return True


def longest_nude_numbers_subsequence(arr):
    max_length = 0
    current_length = 0

    for num in arr:
        if is_nude_number(num):
            current_length += 1
            max_length = max(max_length, current_length)
        else:
            current_length = 0

    return max_length


# Example usage:
arr1 = [34, 34, 2, 2, 3, 333, 221, 32]

print(longest_nude_numbers_subsequence(arr1))
JavaScript
// Function to check if a number is a Nude Number
function isNudeNumber(num) {
    const nudeNumbers = new Set([2, 3, 5, 7]);

    // Check each digit of the number
    while (num > 0) {
        const digit = num % 10;
        // If the digit is not in the set of Nude Numbers, return false
        if (!nudeNumbers.has(digit)) {
            return false;
        }
        num = Math.floor(num / 10);
    }
    // If all digits are Nude Numbers, return true
    return true;
}

// Function to find the length of the longest subsequence of Nude Numbers
function longestNudeNumbersSubsequence(arr) {
    let maxLength = 0; // Initialize the maximum length to 0
    let currentLength = 0; // Initialize the current length to 0

    // Iterate through the array
    for (let num of arr) {
        if (isNudeNumber(num)) {
            // If the number is a Nude Number, increment the current length
            currentLength++;
            // Update the maximum length if needed
            maxLength = Math.max(maxLength, currentLength);
        } else {
            // If the number is not a Nude Number, reset the current length
            currentLength = 0;
        }
    }

    // Return the maximum length of the Nude Numbers subsequence
    return maxLength;
}

// Example usage:
const arr1 = [34, 34, 2, 2, 3, 333, 221, 32];
// Find and print the length of the longest Nude Numbers subsequence in arr1
console.log(longestNudeNumbersSubsequence(arr1)); // Output: 3

Output
4

Time Complexity: O(N * log(num)), where N is the number of elements in the array.

Auxiliary Space: O(1)



Contact Us