Length of longest subsequence consisting of Non-Deficient Numbers
Given an array arr[] consisting of N natural numbers, the task is to find the length of the longest subsequence from the array which does not contain any deficient numbers.
Examples:
Input: arr[] = {13, 55, 240, 32, 24, 27, 56, 80, 100, 330, 89}
Output: 6
Explanation:
Array elements which are not deficient numbers are {240, 24, 56, 80, 100, 330}
Divisors of 13 are {1, 13}. Therefore, sum of divisors = 14, which is less than 26 ( = 2 * 13)
Divisors of 55 are {1, 5, 11, 55}. Therefore, sum of divisors = 72, which is less than 110 ( = 2 * 55).
Divisors of 32 are {1, 2, 4, 8, 16, 32}. Therefore, sum of divisors = 63, which is less than 64 ( = 2 * 32).
Divisors of 27 are {1, 3, 9, 27}. Therefore, sum of divisors = 40, which is less than 54 ( = 2 * 27).
Divisors of 89 are {1, 89}. Therefore, sum of divisors = 90, which is less than 178 ( = 2 * 89).
Therefore, the required count is 6.Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: 6
Explanation: Array elements which are non-deficient numbers are {1, 2, 3, 4, 5, 6}
Approach: The idea to solve the problem is to simply count the number of deficient numbers present in the array. Count of all remaining array elements will be the required length of the longest subsequence. Follow the steps below to solve the problem:
- Initialize a variable, say res, to store the count of array elements that are non-deficient.
- Traverse the array arr[]. For each array element, check if it is a deficient number or not.
- Calculate the sum of all divisors of the current array element and return true, if the sum is less than 2 * arr[i]. Otherwise, return false.
- If found to be false for an array element, increase res.
- After completing the above steps, print the value of res as the required answer.
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 n is // a deficient number or not bool isNonDeficient( int n) { // Stores sum of divisors int sum = 0; // Iterate over the range [1, sqrt(N)] for ( int i = 1; i <= sqrt (n); i++) { // If n is divisible by i if (n % i == 0) { // If divisors are equal, // add only one of them if (n / i == i) { sum = sum + i; } // Otherwise add both else { sum = sum + i; sum = sum + (n / i); } } } return sum >= 2 * n; } // Function to print the longest // subsequence which does not // contain any deficient numbers int LongestNonDeficientSubsequence( int arr[], int n) { // Stores the count of array // elements which are non-deficient int res = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If element is non-deficient if (isNonDeficient(arr[i])) { res += 1; } } // Return the answer return res; } // Driver Code int main() { int arr[] = { 13, 55, 240, 32, 24, 27, 56, 80, 100, 330, 89 }; int N = sizeof (arr) / sizeof (arr[0]); cout << LongestNonDeficientSubsequence(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if n is // a deficient number or not static boolean isNonDeficient( int n) { // Stores sum of divisors int sum = 0 ; // Iterate over the range [1, sqrt(N)] for ( int i = 1 ; i <= Math.sqrt(n); i++) { // If n is divisible by i if (n % i == 0 ) { // If divisors are equal, // add only one of them if (n / i == i) { sum = sum + i; } // Otherwise add both else { sum = sum + i; sum = sum + (n / i); } } } return sum >= 2 * n; } // Function to print the longest // subsequence which does not // contain any deficient numbers static int LongestNonDeficientSubsequence( int arr[], int n) { // Stores the count of array // elements which are non-deficient int res = 0 ; // Traverse the array for ( int i = 0 ; i < n; i++) { // If element is non-deficient if (isNonDeficient(arr[i])) { res += 1 ; } } // Return the answer return res; } // Driver Code public static void main(String[] args) { int arr[] = { 13 , 55 , 240 , 32 , 24 , 27 , 56 , 80 , 100 , 330 , 89 }; int N = arr.length; System.out.print( LongestNonDeficientSubsequence(arr, N)); } } // This code is contributed by splevel62 |
Python3
# Python3 program for the above approach import math # Function to check if n is # a deficient number or not def isNonDeficient(n): # Stores sum of divisors sum = 0 # Iterate over the range [1, sqrt(N)] for i in range ( 1 , int (math.sqrt(n)) + 1 ): # If n is divisible by i if (n % i = = 0 ): # If divisors are equal, # add only one of them if (n / / i = = i): sum = sum + i # Otherwise add both else : sum = sum + i sum = sum + (n / / i) return sum > = 2 * n # Function to print the longest # subsequence which does not # contain any deficient numbers def LongestNonDeficientSubsequence(arr, n): # Stores the count of array # elements which are non-deficient res = 0 # Traverse the array for i in range (n): # If element is non-deficient if (isNonDeficient(arr[i])): res + = 1 # Return the answer return res # Driver Code if __name__ = = "__main__" : arr = [ 13 , 55 , 240 , 32 , 24 , 27 , 56 , 80 , 100 , 330 , 89 ] N = len (arr) print (LongestNonDeficientSubsequence(arr, N)) # This code is contributed by chitranayal |
C#
// C# program for above approach using System; public class GFG { // Function to check if n is // a deficient number or not static bool isNonDeficient( int n) { // Stores sum of divisors int sum = 0; // Iterate over the range [1, sqrt(N)] for ( int i = 1; i <= Math.Sqrt(n); i++) { // If n is divisible by i if (n % i == 0) { // If divisors are equal, // add only one of them if (n / i == i) { sum = sum + i; } // Otherwise add both else { sum = sum + i; sum = sum + (n / i); } } } return sum >= 2 * n; } // Function to print the longest // subsequence which does not // contain any deficient numbers static int LongestNonDeficientSubsequence( int [] arr, int n) { // Stores the count of array // elements which are non-deficient int res = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If element is non-deficient if (isNonDeficient(arr[i])) { res += 1; } } // Return the answer return res; } // Driver code public static void Main(String[] args) { int [] arr = { 13, 55, 240, 32, 24, 27, 56, 80, 100, 330, 89 }; int N = arr.Length; Console.WriteLine( LongestNonDeficientSubsequence(arr, N)); } } // This code is contributed by splevel62. |
Javascript
<script> // Js program for the above approach // Function to check if n is // a deficient number or not function isNonDeficient( n) { // Stores sum of divisors let sum = 0; // Iterate over the range [1, sqrt(N)] for (let i = 1; i <= Math.floor(Math.sqrt(n)); i++) { // If n is divisible by i if (n % i == 0) { // If divisors are equal, // add only one of them if (Math.floor(n / i) == i) { sum = sum + i; } // Otherwise add both else { sum = sum + i; sum = sum + Math.floor(n / i); } } } return sum >= 2 * n; } // Function to print the longest // subsequence which does not // contain any deficient numbers function LongestNonDeficientSubsequence( arr, n) { // Stores the count of array // elements which are non-deficient let res = 0; // Traverse the array for (let i = 0; i < n; i++) { // If element is non-deficient if (isNonDeficient(arr[i])) { res += 1; } } // Return the answer return res; } // Driver Code let arr = [ 13, 55, 240, 32, 24, 27, 56, 80, 100, 330, 89 ]; let N = arr.length; document.write( LongestNonDeficientSubsequence(arr, N)); </script> |
6
Time Complexity: O(N3/2)
Auxiliary Space: O(N)