Dada una array arr[] de N enteros positivos, la tarea es imprimir la longitud de la subsecuencia más larga de la array de modo que todos sus elementos sean números desnudos.
Ejemplos:
Entrada: arr[] = {34, 34, 2, 2, 3, 333, 221, 32 }
Salida: 4
Explicación:
La subsecuencia de número desnudo más larga es {2, 2, 3, 333} y, por lo tanto, la respuesta es 4.
Entrada : arr[] = {456, 44, 104, 133, 39, 325 }
Salida: 1
Explicación:
La subsecuencia de número desnudo más larga es {44} y, por lo tanto, la respuesta es 1.
Enfoque: Para resolver el problema, siga los pasos que se detallan a continuación:
- Recorra la array dada y para cada elemento de la array y verifique si es un número desnudo o no .
- Si el elemento es un Número desnudo , se incluirá en la subsecuencia más larga resultante. Por lo tanto, incremente el recuento de elementos en la subsecuencia en 1 .
- Imprima el valor de conteo después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
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
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 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
<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>
4
Complejidad de tiempo: O(N*log 10 N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA