A deficient number is defined as a positive integer whose sum of proper divisors, excluding the number itself, is smaller than the number. For instance, 8 is considered deficient as the sum of its divisors (1, 2, 4) amounts to 7, which is less than 8.
Input: 10
Output: Deficient
Input: 12
Output: Not Deficient
Explanation:
When considering the integer 10, its proper divisors include 1, 2, and 5. The total sum of these divisors amounts to 8, indicating that 10 falls into the category of deficient numbers. In contrast, for the number 12, the proper divisors encompass 1, 2, 3, 4, and 6, summing up to 16. This sum surpasses the value of 12, thereby categorizing 12 as a non-deficient number.
Approach 1: Using Divisor Sum Comparison:
Algorithm: If a number is deficient
Step 1: Grasp the Issue: Determine the objective: verify if a specified value n is deficient. This involves computing the total of its appropriate divisors and contrasting it with n. A number qualifies as deficient when the total is smaller than n.
Define Step 2: Explanation of Deficient Number: A deficient number is a constructive whole number in which the total of its appropriate divisors (excluding the number itself) is smaller than the number. These appropriate divisors consist of all whole numbers less than the specified number that divide it without any remainder, but do not encompass the number itself. For instance, the number 8 is classified as deficient since the sum of its divisors (1, 2, 4) equals 7, which is lesser than 8.
Step 3: Enter the Numeric Value: Begin by inputting a number n. This numeric value must be a positive integer, as the concept of deficiency is solely applicable to positive integers.
Initialize Variables: Create a variable named sum to hold the total sum of the divisors. Begin by setting sum to 0 prior to commencing the divisor computation.
Step 5: Identify Suitable Divisors: Suitable divisors of a given number refer to all whole numbers that are less than n and can evenly divide n with a remainder of 0. Iterate through each integer ranging from 1 to n-1.
For every integer i, validate whether n modulo i equals zero (i.e., n is divisible by i). If this condition is met, include i in the sum total.
Calculate the Sum of Divisors: By the conclusion of the iteration, the variable 'sum' will contain the cumulative sum of all valid divisors of the number n.
Step 7: Check if the sum is less than n. If the sum is less than n, then n is considered a deficient number as the total of its proper divisors is smaller than n. On the other hand, if the sum is greater than or equal to n, then n is not classified as a deficient number.
Output the Outcome: Display the outcome by printing "Deficient" when the sum is less than n; otherwise, print "Not Deficient".
Algorithm: If a number is not deficient
Step 1: Grasp the Issue: A number is considered non-deficient when the total of its proper divisors (excluding the number itself) equals or exceeds the number. The objective is to verify if this criterion is met for a specified number n.
Step 2: Provide the Input: Enter a positive integer value for 'n'. Only positive integers are acceptable for this calculation.
Step 3: Variable Initialization: Establish a variable named sum to collect the sum of valid divisors. Begin by setting it to zero: sum=0
Step 4: Recognize Proper Factors: Proper factors refer to integers less than n that can divide n evenly. Employ a loop to cycle through numbers ranging from 1 to n-1.
For each number i, check if n modi=0. If the condition is true, i is a proper divisor. Add i to sum.
Calculate the Sum of Divisors: Once the loop finishes executing, the variable sum will store the total sum of all the proper divisors of the given number, n.
Compare the total sum with the number n: If the sum is equal to or greater than n, it indicates that the number n is not deficient as it has ample or more divisors compared to n. However, if the sum is less than n, then the number is considered deficient.
Output the Outcome: Showcase the outcome as "Not Deficient" when the sum is greater than or equal to n. Otherwise, display "Deficient".
Program:
#include <iostream>
using namespace std;
bool isDeficient(int n) {
int sum = 0;
for (int i = 1; i < n; ++i) {
if (n % i == 0) {
sum += i;
}
}
return sum < n;
}
int main() {
int inputs[] = {10, 12};
for (int n : inputs) {
if (isDeficient(n)) {
cout << n << " is Deficient" << endl;
} else {
cout << n << " is Not Deficient" << endl;
}
}
return 0;
}
Output:
10 is Deficient
12 is Not Deficient
Complexity Analysis:
Time Complexity:
Determining if a number is deficient has a time complexity of O(n), with 'n' representing the given input number. This is due to the necessity of examining every integer between 1 and n-1 to identify the divisors. Consequently, the procedure requires traversing through all values up to n.
Space Complexity:
The space complexity for checking if a number is deficient is O(1) because the process only needs a constant amount of additional space. It relies on a solitary variable for adding up divisors and doesn't hold onto any substantial data structures, no matter the size of the input.
Approach: Efficient Divisor Calculation (Using √n)
The above approach loops through all numbers from 111 to n-1n-1n-1 to find proper divisors, which has a time complexity of O(n)O(n)O(n). A more efficient method can reduce this complexity by considering the divisors in pairs and iterating only up to n\sqrt{n}n.
