# 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.