Anti-perfect Number in Java
The following article explores the concept of anti-perfect numbers, a class of numbers that defy the conventional expectation of summing up to a value greater than themselves through the sum of their proper divisors. Anti-perfect numbers are derived from the fundamental notion of divisors, which are the numbers that evenly divide an integer, leaving no remainder. They exhibit a distinct behavior where the sum of proper divisors falls short of the number, rendering them mathematically deficient.
Example 1:
Input: N = 6
Output: Yes
Explanation: The proper divisors of 6 are 1, 2, and 3.
The sum of the reverse digits of each divisor is:
Reverse(1) = 1
Reverse(2) = 2
Reverse(3) = 3
The sum of these reverse digits is 1 + 2 + 3 = 6, which equals N.
Therefore, the output is "Yes".
Example 2:
Input: N = 28
Output: No
Explanation: For N = 28:
The proper divisors of 28 are 1, 2, 4, 7, and 14.
The sum of the reverse digits of each divisor is:
Reverse(1) = 1
Reverse(2) = 2
Reverse(4) = 4
Reverse(7) = 7
Reverse(14) = 41
The sum of these reverse digits is 1 + 2 + 4 + 7 + 41 = 55, which does not equal N. Therefore, the output is "No".
Recursive Approach
Algorithm
Step 1: Iterate through each proper divisor of the given number.
Step 2: Calculate the sum of the reverse digits of each divisor.
Step 3: If the sum of reverse digits equals the original number, return true (indicating it's an anti-perfect number); otherwise, return false.
Step 4: Print "Yes" if the number is anti-perfect; otherwise, print "No".
Here is an implementation of finding an anti-perfect number using a recursive approach :
FileName:AntiPerfectNumberApproach1.java
public class AntiPerfectNumberApproach1 { // Function to reverse digits of a number static int reverse(int num) { int reversedNum = 0; while (num != 0) { int digit = num % 10; reversedNum = reversedNum * 10 + digit; num /= 10; } return reversedNum; } // Function to calculate the sum of the reverse of proper divisors static int sumOfReverseDivisors(int num) { int sum = 1; // 1 is always a divisor for (int i = 2; i <= Math.sqrt(num); i++) { if (num % i == 0) { if (i == (num / i)) sum += reverse(i); else sum += (reverse(i) + reverse(num / i)); } } return sum; } // Function to check if a number is anti-perfect static boolean isAntiPerfect(int n) { return sumOfReverseDivisors(n) == n; } public static void main(String[] args) { int N = 28; if (isAntiPerfect(N)) System.out.println("Yes"); else System.out.println("No"); } }
Output:
No
Complexity analysis: The time complexity of the above approach is O(sqrt(N) * log(N)), where N is the input number. The space complexity is O(1), as the space usage remains constant regardless of the input size.
Using StringBuilder
Algorithm
Step 1: Iterate through each number ` i' from 2 to the square root of the given number.
Step 2: If `i' divides the given number evenly, reverse the digits and add the result to the sum.
Step 3: If `i' is not equal to the quotient of the given number, reverse the digits and add the result to the sum.
Step 4: Check if the sum equals the given number. If so, return true.
Here is an implementation of finding an anti-perfect number using stringbuilder :
FileName:AntiPerfectNumberApproach2.java
import java.util.*; public class AntiPerfectNumberApproach2 { // Function to calculate the sum of the reverse of proper divisors static int sumOfReverseDivisors(int num) { int sum = 1; // 1 is always a divisor for (int i = 2; i <= Math.sqrt(num); i++) { if (num % i == 0) { StringBuilder sb = new StringBuilder(String.valueOf(i)); int reverseI = Integer.parseInt(sb.reverse().toString()); sum += reverseI; if (i != (num / i)) { sb = new StringBuilder(String.valueOf(num / i)); int reverseDiv = Integer.parseInt(sb.reverse().toString()); sum += reverseDiv; } } } return sum; } // Function to check if a number is anti-perfect static boolean isAntiPerfect(int n) { return sumOfReverseDivisors(n) == n; } public static void main(String[] args) { int N = 28; if (isAntiPerfect(N)) System.out.println("Yes"); else System.out.println("No"); } }
Output:
No
Complexity analysis: The above approach has a time complexity of O(sqrt(N) * log(N)) due to iterating through proper divisors and performing reverse operations and a space complexity of O(1) due to constant memory usage for variable storage.