Sum of Digit is Palindrome or not in Java
Given an integer N. The task is to find the sum of digits is palindrome or not. A palindrome is a number or a string that reads the same backward as forward. We compute the sum of its digits and then check if this sum is a palindrome or not.
Example 1
Input: N = 12321
Output: Yes
Explanation: The sum of digits is (1 + 2 + 3 + 2 + 1) = 9, which is a palindrome.
Example 2
Input: N = 12345
Output: No
Explanation: The sum of digits is (1 + 2 + 3 + 4 + 5) = 15, which is not a palindrome.
Example 3
Input: 74
Output: Yes
Explanation: The sum of digits is (7 + 4) = 11, which is palindrome.
Example 4
Input: N = 123
Output: No
Explanation: The sum of digits is (1 + 2 + 3) = 6, which is not a palindrome.
Approach 1: Using Brute Force
The brute force approach directly compares characters from both ends of the sum of digits to check if it's a palindrome.
Algorithm
Step 1: Compute the sum of digits of the given number.
Step 2: Convert the sum to a string.
Step 3: Compare characters from both ends towards the middle of the string to check if it's a palindrome.
FileName: SumOfDigitsPalindromeBruteForce.java
public class SumOfDigitsPalindromeBruteForce { public static void main(String[] args) { int number = 74; int sum = sumOfDigits(number); // Calculate the sum of digits boolean isPalindrome = isPalindromeBruteForce(sum); // Check if the sum is a palindrome System.out.println(isPalindrome); // Print the result } // Function to compute the sum of digits private static int sumOfDigits(int number) { int sum = 0; while (number > 0) { sum += number % 10; // Add the last digit to the sum number /= 10; // Remove the last digit } return sum; } // Brute force approach to check if a number is a palindrome private static boolean isPalindromeBruteForce(int number) { String sumStr = String.valueOf(number); // Convert the sum to a string for (int i = 0; i < sumStr.length() / 2; i++) { // Iterate only up to half of the string length if (sumStr.charAt(i) != sumStr.charAt(sumStr.length() - 1 - i)) { // Compare characters from both ends return false; // Not a palindrome, return false } } return true; // If all characters match, it's a palindrome } }
Output
true
Time Complexity: The time complexity of an algorithm is O(n/2) where n is the number of digits in the sum, as we iterate through half of the digits to check for palindrome property.
Space Complexity: The space complexity of an algorithm is O(n) where n is the number of digits in the sum, as we store the sum as a string.
Approach 2: Using Recursion
The recursive approach divides the problem into smaller subproblems by checking characters from both ends of the sum of digits.
Algorithm
Step 1: Compute the sum of digits of the given number.
Step 2: Convert the sum to a string.
Step 3: Use a recursive helper function to check if the string is a palindrome by comparing characters from both ends towards the middle recursively.
FileName: SumOfDigitsPalindromeRecursion.java
public class SumOfDigitsPalindromeRecursion { public static void main(String[] args) { int number = 74; int sum = sumOfDigits(number); // Calculate the sum of digits boolean isPalindrome = isPalindromeRecursive(sum); // Check if the sum is a palindrome System.out.println(isPalindrome); // Print the result } // Function to compute the sum of digits private static int sumOfDigits(int number) { int sum = 0; while (number > 0) { sum += number % 10; // Add the last digit to the sum number /= 10; // Remove the last digit } return sum; } // Recursive approach to check if a number is a palindrome private static boolean isPalindromeRecursive(int number) { String sumStr = String.valueOf(number); // Convert the sum to a string return isPalindromeRecursiveHelper(sumStr, 0, sumStr.length() - 1); } // Recursive helper function to check if a string is a palindrome private static boolean isPalindromeRecursiveHelper(String str, int left, int right) { if (left >= right) { return true; // Base case: If left pointer crosses or equals right pointer, it's a palindrome } if (str.charAt(left) != str.charAt(right)) { return false; // If characters at left and right pointers don't match, it's not a palindrome } // Recur for the substring by moving left pointer forward and right pointer backward return isPalindromeRecursiveHelper(str, left + 1, right - 1); } }
Output
true
Time Complexity: The time complexity of an algorithm is O(n) where n is the number of digits in the sum, as we check each character of the sum string recursively.
Space Complexity: The space complexity of an algorithm is O(n) where n is the number of digits in the sum, as we store the sum as a string and use recursion which consumes additional memory on the function call stack.