Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
1. Using Loop to Check Perfect Number in Java
2.1.
Java
3.
2. Using Square Root to Check Perfect Number in Java
3.1.
Java
4.
3. Recursive Approach to Check Perfect Number in Java
4.1.
Java
5.
Time and Space Complexity
5.1.
Using Loop to Check Perfect Number
5.2.
Using Square Root to Check Perfect Number
5.3.
Recursive Approach to Check Perfect Number
6.
Frequently Asked Questions
6.1.
What is a perfect number?
6.2.
Why use the square root method to check for perfect numbers?
6.3.
Can the recursive method be optimized further for performance?
7.
Conclusion
Last Updated: May 25, 2024
Easy

Perfect Number in Java

Author Riya Singh
0 upvote

Introduction

A perfect number is a positive integer that is equal to the sum of its proper divisors (excluding itself). In other words, if we add up all the factors of a number (excluding the number itself) & the result is equal to the original number, then it is considered a perfect number. For example, 6 is a perfect number because its proper divisors (1, 2, & 3) add up to 6. 

Perfect Number in Java

In this article, we will learn different ways to check if a number is a perfect number using Java programming language. We will cover various approaches such as using loops, square root optimization, & recursive techniques. Additionally, we will analyze the time & space complexity of each approach.

1. Using Loop to Check Perfect Number in Java

To determine whether a number is perfect in Java, one straightforward method is to use a loop. The process involves iterating over numbers that are less than the target number & summing those that are its divisors. A divisor is a number that divides another without leaving a remainder.

Here’s how you can implement this:

  • Java

Java

public class PerfectNumber {
public static boolean isPerfect(int number) {
int sum = 0;
// Start loop from 1 and check up to the number-1
for (int i = 1; i < number; i++) {
if (number % i == 0) {
sum += i; // Add divisor if it divides number completely
}
}
// Check if sum of divisors is equal to the number itself
return sum == number;
}

public static void main(String[] args) {
int testNumber = 28;
if (isPerfect(testNumber)) {
System.out.println(testNumber + " is a perfect number.");
} else {
System.out.println(testNumber + " is not a perfect number.");
}
}
}

Output

28 is a perfect number.

In this code, we define a method isPerfect that takes an integer number & returns a boolean value indicating whether it is perfect or not. We initiate a sum variable at 0 & iterate through numbers from 1 to one less than the target number. For each iteration, if the current number is a divisor (i.e., number % i == 0), we add it to the sum. After the loop, if the sum of these divisors equals the original number, the number is perfect, & the method returns true; otherwise, it returns false.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

2. Using Square Root to Check Perfect Number in Java

An optimization to the loop method for checking perfect numbers involves using the square root of the number. This approach significantly reduces the number of iterations required, as you only check up to the square root of the number instead of the number itself.

Implementation in Java:

  • Java

Java

public class PerfectNumberOptimized {
public static boolean isPerfect(int number) {
int sum = 1; // Start sum at 1 because 1 is a divisor for all numbers
// Loop from 2 to the square root of number
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
sum += i; // Add the divisor
if (i != number / i) {
sum += number / i; // Add the corresponding divisor greater than the square root
}
}
}
// Check if the sum of divisors is equal to the number
return number > 1 && sum == number;
}

public static void main(String[] args) {
int testNumber = 28;
if (isPerfect(testNumber)) {
System.out.println(testNumber + " is a perfect number.");
} else {
System.out.println(testNumber + " is not a perfect number.");
}
}
}

Output

28 is a perfect number.


In this implementation, the isPerfect method starts with a sum initialized at 1. It then iterates from 2 up to the square root of the target number, checking if each number is a divisor. If it is, the divisor is added to the sum. Additionally, the corresponding divisor greater than the square root (calculated as number / i) is also added unless it's the same as the smaller divisor. This helps in accounting for all divisors without iterating through every single number up to the target.

3. Recursive Approach to Check Perfect Number in Java

A recursive method can also be used to determine if a number is perfect. This approach breaks down the problem into smaller, manageable parts by repeatedly calling the function within itself. Here, we adapt the idea of checking for divisors recursively, summing them up, and comparing the sum to the original number.

Here's how you can implement this recursively in Java:

  • Java

Java

public class PerfectNumberRecursive {
// Helper function to find divisors & sum them recursively
private static int sumDivisors(int number, int i) {
// Base case: if i is equal to number, return 0
if (i == number) {
return 0;
} else if (number % i == 0) {
return i + sumDivisors(number, i + 1); // Add i if it is a divisor
} else {
return sumDivisors(number, i + 1); // Continue to next i if not a divisor
}
}
// Function to check if number is perfect
public static boolean isPerfect(int number) {
// Call recursive helper starting with 1
int sum = sumDivisors(number, 1);
return sum == number;
}
public static void main(String[] args) {
int testNumber = 28;
if (isPerfect(testNumber)) {
System.out.println(testNumber + " is a perfect number.");
} else {
System.out.println(testNumber + " is not a perfect number.");
}
}
}

Output

28 is a perfect number.


In this code, the sumDivisors method is used to recursively find and sum all divisors of the given number, except the number itself. It starts from 1 and continues to the number-1. If the current index (i) divides the number without a remainder, it is added to the sum. The recursion continues by increasing i until it equals the number.

Time and Space Complexity

Understanding the time & space complexity of algorithms is crucial when assessing their efficiency. Let's analyze the complexities of the three methods we discussed for checking if a number is perfect in Java.

Using Loop to Check Perfect Number

  • Time Complexity: The time complexity of this method is O(n), where n is the number being checked. This is because the algorithm iterates through all numbers from 1 to n-1 to find the divisors.
     
  • Space Complexity: The space complexity is O(1), as the method uses a constant amount of space regardless of the input size.

Using Square Root to Check Perfect Number

  • Time Complexity: This method improves the time complexity to O(√n) by only iterating up to the square root of the number. It's more efficient because it reduces the number of iterations needed to find the divisors.
     
  • Space Complexity: The space complexity remains O(1), similar to the loop method, as it uses a fixed amount of extra space.

Recursive Approach to Check Perfect Number

  • Time Complexity: The recursive method also has a time complexity of O(n) because, in the worst case, it needs to check each number up to n-1 for divisibility.
     
  • Space Complexity: The space complexity can increase to O(n), especially in cases where the recursion depth approaches n, because each recursive call adds a layer to the call stack.

Frequently Asked Questions

What is a perfect number?

A perfect number is a positive integer that is equal to the sum of its proper divisors, excluding the number itself. For example, 6 is perfect because its divisors are 1, 2, and 3, and 1 + 2 + 3 = 6.

Why use the square root method to check for perfect numbers?

Using the square root method reduces the number of calculations significantly, as it only requires checking up to the square root of the number. This makes the process faster especially for larger numbers.

Can the recursive method be optimized further for performance?

While the recursive method is elegant, it is generally not as efficient due to its high space complexity. Optimizing it might involve limiting recursion depth or switching to an iterative approach to reduce stack usage.

Conclusion

In this article, we have learned various methods to check if a number is a perfect number in Java. We explored a straightforward loop method, an optimized approach using square roots, and a recursive method. We discussed the pros & cons of each, especially in terms of their time and space complexity. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
Functional Interface in Java
Next article
Methods to Print New Line in Java
Live masterclass