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:

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    bool isNonDeficient(int n) {          int sum = 0;             for (int i = 1; i <= sqrt(n); i++) {                     if (n % i == 0) {                                          if (n / i == i) {                 sum = sum + i;             }                             else {                 sum = sum + i;                 sum = sum + (n / i);             }         }     }     return sum >= 2 * n; }    int LongestNonDeficientSubsequence(int arr[], int n) {               int res = 0;             for (int i = 0; i < n; i++) {                     if (isNonDeficient(arr[i])) {             res += 1;         }     }             return res; }    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; }

Time Complexity: O(N^3/2)
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)