Abundant number in Java
An Abundant Number in Java, or any other programming language, is a fascinating mathematical concept that can be explored and identified through code. To comprehend what an abundant number is, we first need to understand its definition.
An abundant number, also known as an excessive number, is a positive integer that is smaller than the sum of its proper divisors. Proper divisors of a number are the positive divisors excluding the number itself.
Example 1:
Input: Checking if 24 is an abundant number.
Output: 24 is an abundant number.
Explanation:
In this example we are checking if the number 24 is an abundant number. We calculate the sum of its proper divisors which are 1, 2, 3, 4, 6, 8, and 12. The sum of these divisors is 1 + 2 + 3 + 4 + 6 + 8 + 12 = 36 which is greater than 24. Therefore, the output correctly states that 24 is an abundant number.
Example 2:
Input: Checking if 16 is an abundant number.
Output: 16 is not an abundant number.
Explanation:
In this example we are checking if the number 16 is an abundant number. The divisors of 16 are 1, 2, 4, 8, and 16. The sum of its proper divisors (excluding 16) is 1 + 2 + 4 + 8 = 15, which is less than 16. Therefore, the output correctly states that 16 is not an abundant number.
Example 3:
Input: Checking if 30 is an abundant number.
Output: 30 is an abundant number.
Explanation:
In this example we are checking if the number 30 is an abundant number. The divisors of 30 are 1, 2, 3, 5, 6, 10, 15, and 30. The sum of its proper divisors (excluding 30) is 1 + 2 + 3 + 5 + 6 + 10 + 15 = 42, which is greater than 30. Therefore, the output correctly states that 30 is an abundant number.
Approach 1: Using Iterative
ALGORITHM:
Step 1: Begin by creating a Java class named AbundantNumber.
Step 2: Within this class, define a function named sumOfDivisors that takes a single integer n as input.
Step 3: Initialize an integer variable called sum to 1 as all numbers are divisible by 1.
Step 4: Set up a for loop to iterate through numbers from 2 up to n/2, including both 2 and n/2.
Step 5: Inside the loop, check if n is evenly divisible by the current number i. You can do this by using the modulo operator: n % i == 0.
Step 6: If the condition in step 5 is satisfied add the value of i to the sum variable.
Step 7: Continue the loop until you've checked all numbers from 2 to n/2.
Step 8: After the loop completes, return the final value of the sum variable.
Step 9: Now, define another function named isAbundant that also takes an integer n as input.
Step 10: Inside this function calculate the sum of divisors by invoking the sumOfDivisors function with n as the argument.
Step 11: Next, compare the calculated sum of divisors from step 10 with the original number n.
Step 12: If the sum of divisors is greater than n return true. This indicates that n is an abundant number.
Step 13: If the sum of divisors is not greater than n return false, indicating that n is not an abundant number.
Step 14: In the main function, start by creating an array named numbersToCheck that contains the integers you wish to evaluate for abundance (e.g., {24, 16, 30}).
Step 15: Set up a loop to iterate through each number in the numbersToCheck array.
Step 16: For each number in the array call the isAbundant function to determine whether it is an abundant number.
Step 17: After calling isAbundant, check the result:
Step 17.1: If the result is true print a message indicating that the number is an abundant number.
Step 17.2: If the result is false print a message indicating that the number is not an abundant number.
Step 18: Continue this process for all the numbers in the numbersToCheck array.
Implementation:
The Implementation of the above steps given below as follows
FileName: AbundantNumber.java
import java.util.*;
public class AbundantNumber
{
// Function to calculate the sum of proper divisors
public static int sumOfDivisors(int n)
{
int sum=1;
for(int i=2;i<=n/2;i++)
{
if(n%i==0)
{
sum+=i;
}
}
return sum;
}
// Function to check if a number is abundant
public static boolean isAbundant(int n) {
return sumOfDivisors(n) > n; // Compare the sum of divisors with 'n' to determine abundance
}
public static void main(String[] args) {
int[] numbersToCheck = {24, 16, 30};
for (int number : numbersToCheck) {
if (isAbundant(number)) {
System.out.println(number + " is an abundant number.");
} else {
System.out.println(number + " is not an abundant number.");
}
}
}
}
Output:
24 is an abundant number. 16 is not an abundant number. 30 is an abundant number.
Complexity Analysis:
Time Complexity:
The time complexity of the above code is O(n^2) because the sumOfDivisors function iterates through numbers up to n/2, and it's called for each number in the numbersToCheck array.
Space Complexity:
The space complexity is O(1) because the memory usage remains constant regardless of the input size.
Approach 2: Using Recursion
ALGORITHM:
Step 1: Begin by creating a Java class named AbundantNumber.
Step 2: Within this class define a recursive function named sumOfDivisors that takes two parameters n and the current divisor being considered.
Step 3: In the sumOfDivisors function include a base case If divisor reaches 1 return 1. It is because 1 is a divisor for all numbers so the sum is always 1 in this case.
Step 4: Inside the sumOfDivisors function check if the current divisor evenly divides n.
Step 5: If the condition in step 4 is met, add the current divisor to the result of a recursive call to sumOfDivisors with n and divisor-1 as arguments. This step accumulates the sum of proper divisors.
Step 6: If the condition in step 4 is not met (the divisor does not evenly divide n), proceed to the next smaller divisor by making a recursive call to sumOfDivisors with n and divisor-1 as arguments.
Step 7: Now, define another function named isAbundant that takes an integer n as input.
Step 8: Inside the isAbundant function calculate the sum of divisors by invoking the sumOfDivisors function with n as the number and n/2 as the initial divisor. Start with the highest possible divisor (n/2).
Step 9: Next, compare the calculated sum of divisors from step 8 with the original number n.
Step 10: If the sum of divisors is greater than n return true. This indicates that n is an abundant number.
Step 11: If the sum of divisors is not greater than n return false, indicating that n is not an abundant number.
Step 12: In the main function, create an array named numbersToCheck that contains the integers you wish to evaluate for abundance (e.g., {24, 16, 30}).
Step 13: Set up a loop to iterate through each number in the numbersToCheck array.
Step 14: For each number in the array call the isAbundant function to determine whether it is an abundant number.
Step 15: After calling isAbundant, check the result:
Step 16: If the result is true, print a message indicating that the number is an abundant number.
Step 17: If the result is false, print a message indicating that the number is not an abundant number.
Step 18: Continue this process for all the numbers in the numbersToCheck array.
Implementation:
The implementation of the above steps given below
FileName: AbundantNumber.java
import java.util.*;
public class AbundantNumber
{
// Function to calculate the sum of proper divisors recursively
public static int sumOfDivisors(int n, int divisor) {
if (divisor==1)
{
return 1;
// Base case: 1 is a divisor for all numbers, so the sum is 1.
}
if (n%divisor==0)
{
return divisor+sumOfDivisors(n,divisor-1);
// If divisor evenly divides n, add it to the sum.
}
return sumOfDivisors(n, divisor - 1); // Continue with the next divisor.
}
// Function to check if a number is abundant
public static boolean isAbundant(int n) {
int sum = sumOfDivisors(n, n / 2); // Start with the highest possible divisor (n/2).
return sum > n; // Compare the sum of divisors with n to determine abundance.
}
public static void main(String[] args) {
int[] numbersToCheck = {24, 16, 30};
for (int number : numbersToCheck) {
if (isAbundant(number)) {
System.out.println(number + " is an abundant number.");
} else {
System.out.println(number + " is not an abundant number.");
}
}
}
}
Output:
24 is an abundant number. 16 is not an abundant number. 30 is an abundant number.
Complexity Analysis:
Time Complexity:
The overall time complexity of the code is O(k * n) where k is the number of elements in the numbersToCheck array and n is the maximum value among those numbers.It is because you iterate through the numbersToCheck array in the main function, and for each element, you call the sumOfDivisors function which has a time complexity of O(n).
Space Complexity:
The space complexity is determined by the function call stack during recursive calls in sumOfDivisors. In the worst case, the function can be called recursively n times (for the largest value in numbersToCheck). Therefore, the space complexity of the code is O(n) due to the recursive function calls.
Approach 3: Using Stack
ALGORITHM:
Step 1: Create a Java class named AbundantNumber.
Step 2: Inside the class, define a function sumOfDivisors that takes an integer n as input.
Step 3: Initialize an integer variable sum to 1 since all numbers are divisible by 1.
Step 4: Create a Stack
Step 5: Iterate through numbers from 2 up to n/2 using a for loop.
Step 6: For each i in the iteration check if n is evenly divisible by i.
Step 7: If n is divisible by i push i onto the divisors stack and add i to the sum.
Step 8: After the loop, display the divisors in the order they were found using a while loop that pops elements from the divisors stack and prints them.
Step 9: Return the sum of proper divisors.
Step 10: Define a function isAbundant that takes an integer n as input.
Step 11: Inside the isAbundant function, calculate the sum of divisors by calling the sumOfDivisors function with n as the argument.
Step 12: Compare the calculated sum of divisors with n.
Step 13: If the sum of divisors is greater than n return true, indicating that n is an abundant number.
Step 14: If the sum of divisors is not greater than n return false, indicating that n is not an abundant number.
Step 15: In the main function, create an array named numbersToCheck containing the integers you want to evaluate for abundance.
Step 16: Iterate through each number in the numbersToCheck array.
Step 17: For each number call the isAbundant function to determine whether it's an abundant number.
Step 18: If a number is abundant, print a message stating that it is an abundant number. Otherwise print a message stating that it is not an abundant number.
Implementation:
The implementation of the above steps given below
FileName: AbundantNumber.java
import java.util.Stack;
public class AbundantNumber
{
// Function to calculate the sum of proper divisors
public static int sumOfDivisors(int n)
{
int sum=1;
// Start with 1 since all numbers are divisible by 1
Stack divisors=new Stack<>();
// Create a stack to track divisors
// Iterate through numbers from 2 up to n/2
for(int i=2;i<=n/2;i++)
{
if(n%i==0)
{
divisors.push(i); // Push the divisor onto the stack
sum+=i; // Add the divisor to the sum
}
}
// Display the divisors in the order they were found (last-in, first-out)
System.out.print("Divisors of "+n+": ");
while(!divisors.isEmpty())
{
System.out.print(divisors.pop() + " ");
}
System.out.println(); // Move to the next line for clarity
return sum;
}
// Function to check if a number is abundant
public static boolean isAbundant(int n) {
return sumOfDivisors(n) > n;
}
public static void main(String[] args) {
int[] numbersToCheck = {24, 16, 30};
for (int number : numbersToCheck) {
if (isAbundant(number)) {
System.out.println(number + " is an abundant number.");
} else {
System.out.println(number + " is not an abundant number.");
}
}
}
}
Output:
Divisors of 24: 12 8 6 4 3 2 24 is an abundant number. Divisors of 16: 8 4 2 16 is not an abundant number. Divisors of 30: 15 10 6 5 3 2 30 is an abundant number.
Complexity Analysis:
Time Complexity:
In this implementation, the sumOfDivisors function is a critical component responsible for iterating through numbers from 2 up to n/2. In the worst case scenario, when 'n' has a large number of divisors, this function runs 'n/2' times. Within this loop, the operations conducted, including simple arithmetic and stack operations, are all considered constant time operations. As a result, the overall time complexity of this implementation is O(n/2) in the worst case, which can be simplified to O(n).
Space Complexity:
The primary contributor to the space complexity in this implementation is the Stack
Approach 4: Using HashMap
ALGORITHM:
Step 1: Begin by creating a Java class named AbundantNumber.
Step 2: Inside the class define a function named sumOfDivisors that takes an integer n as input and returns a HashMap.
Step 3: Initialize a HashMap
Step 4: Set the initial key-value pair in divisorSumMap as (1, 1), as all numbers are divisible by 1.
Step 5: Create a for loop to iterate through numbers from 2 up to n/2.
Step 6: Within the loop check if n is evenly divisible by the current number i.
Step 7: If n is divisible by i add i to the sum of divisors stored in divisorSumMap. If i is not already a key in the map initialize it with the divisor's value.
Step 8: After the loop return the divisorSumMap containing divisors and their sums.
Step 9: Define a function named isAbundant that takes an integer n as input.
Step 10: Inside the isAbundant function call the sumOfDivisors function to get the HashMap of divisors and their sums.
Step 11: Calculate the sum of divisors by summing the values from the divisorSumMap.
Step 12: Compare the calculated sum of divisors with the original number n.
Step 13: If the sum of divisors is greater than n return true, indicating that n is an abundant number.
Step 14: If the sum of divisors is not greater than n return false, indicating that n is not an abundant number.
Step 15: In the main function, create an array named numbersToCheck containing the integers you want to evaluate for abundance.
Step 16: Set up a loop to iterate through each number in the numbersToCheck array.
Step 17: For each number call the isAbundant function to determine whether it's an abundant number.
Step 18: If a number is abundant print a message stating that it is an abundant number. Otherwise, print a message stating that it is not an abundant number.
Implementation:
The implementation of the above steps given below
FileName: AbundantNumber.java
import java.util.*;
public class AbundantNumber
{
// Function to calculate the sum of proper divisors and store them in a HashMap
public static Map sumOfDivisors(int n)
{
Map divisorSumMap=new HashMap<>();
divisorSumMap.put(1,1);
// Initialize with 1 as all numbers are divisible by 1
// Iterate through numbers from 2 up to n/2
for(int i=2;i<=n/2;i++)
{
if(n%i==0)
{
divisorSumMap.put(i,i+divisorSumMap.getOrDefault(i,0));
// Add the divisor to the sum
}
}
return divisorSumMap;
}
// Function to check if a number is abundant
public static boolean isAbundant(int n)
{
Map divisorSumMap=sumOfDivisors(n);
// Calculate the sum of divisors from the HashMap
int sum=divisorSumMap.values().stream().mapToInt(Integer::intValue).sum();
return sum>n;
}
public static void main(String[] args)
{
int[] numbersToCheck={24,16,30};
for(int number:numbersToCheck)
{
if (isAbundant(number))
{
System.out.println(number+" is an abundant number.");
}
else
{
System.out.println(number+" is not an abundant number.");
}
}
}
}
Output:
24 is an abundant number. 16 is not an abundant number. 30 is an abundant number.
Complexity Analysis:
Time Complexity:
The time complexity is O(n) in the worst case, where 'n' is the input number being checked for abundance. This is primarily due to the loop that iterates from 2 up to 'n/2' in the sumOfDivisors function. In the worst case, this loop can run 'n/2' times, resulting in a linear time complexity.
Space Complexity:
The space complexity is also O(n) in the worst case. This is because the divisorSumMap HashMap can store divisors and their sums for each number up to 'n/2'. Therefore, the space required is proportional to the input 'n'. Additionally, other memory usage in the algorithm remains constant and does not depend on 'n'.