Given a number N. The task is to find the sum of all N-digit palindromes.
Examples:
Input: N = 2 Output: 495 Explanation: 11 + 22 + 33 + 44 + 55 + 66 + 77 + 88 + 99 = 495 Input: N = 7 Output: 49500000000
Naive Approach:
Run a loop from 10^(n-1) to 10^(n) – 1 and check when the current number is palindrome or not. If it adds its value to the answer.
Below is the implementation of the above approach:
CPP
// C++ program for the// above approach#include <bits/stdc++.h>using namespace std;// Function to check// palindromebool isPalindrome(string& s){ int left = 0, right = s.size() - 1; while (left <= right) { if (s[left] != s[right]) { return false; } left++; right--; } return true;}// Function to calculate// the sum of n-digit// palindromelong long getSum(int n){ int start = pow(10, n - 1); int end = pow(10, n) - 1; long long sum = 0; // Run a loop to check // all possible palindrome for (int i = start; i <= end; i++) { string s = to_string(i); // If palindrome // append sum if (isPalindrome(s)) { sum += i; } } return sum;}// Driver codeint main(){ int n = 1; long long ans = getSum(n); cout << ans << '\n'; return 0;} |
Java
// Java program for the// above approachimport java.util.*;class GFG{// Function to check// palindromestatic boolean isPalindrome(String s){ int left = 0, right = s.length() - 1; while (left <= right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true;}// Function to calculate// the sum of n-digit// palindromestatic long getSum(int n){ int start = (int) Math.pow(10, n - 1); int end = (int) (Math.pow(10, n) - 1); long sum = 0; // Run a loop to check // all possible palindrome for (int i = start; i <= end; i++) { String s = String.valueOf(i); // If palindrome // append sum if (isPalindrome(s)) { sum += i; } } return sum;}// Driver codepublic static void main(String[] args){ int n = 1; long ans = getSum(n); System.out.print(ans);}}// This code is contributed by 29AjayKumar |
Python
# Python program for the above approach import math# Function to check # palindrome def isPalindrome(s): left = 0 right = len(s) - 1 while (left <= right): if (s[left] != s[right]): return False left = left + 1 right = right - 1 return True# Function to calculate # the sum of n-digit # palindrome def getSum(n): start = int(math.pow(10, n - 1)) end = int(math.pow(10, n)) - 1 sum = 0 # Run a loop to check # all possible palindrome for i in range(start, end + 1): s = str(i) # If palindrome # append sum if (isPalindrome(s)): sum = sum + i return sum# Driver code n = 1ans = getSum(n)print(ans)# This code is contributed by Sanjit_Prasad |
C#
// C# program for the above approachusing System;class GFG{ // Function to check // palindrome static bool isPalindrome(string s) { int left = 0, right = s.Length - 1; while (left <= right) { if (s[left] != s[right]) { return false; } left++; right--; } return true; } // Function to calculate // the sum of n-digit // palindrome static long getSum(int n) { int start = (int) Math.Pow(10, n - 1); int end = (int) (Math.Pow(10, n) - 1); long sum = 0; // Run a loop to check // all possible palindrome for (int i = start; i <= end; i++) { string s = i.ToString();; // If palindrome // append sum if (isPalindrome(s)) { sum += i; } } return sum; } // Driver code public static void Main() { int n = 1; long ans = getSum(n); Console.Write(ans); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// JavaScript program for the// above approach// Function to check// palindromefunction isPalindrome(s){ var left = 0, right = s.length - 1; while (left <= right) { if (s[left] != s[right]) { return false; } left++; right--; } return true;}// Function to calculate// the sum of n-digit// palindromefunction getSum(n){ var start = Math.pow(10, n - 1); var end = Math.pow(10, n) - 1; var sum = 0; // Run a loop to check // all possible palindrome for (var i = start; i <= end; i++) { var s = (i.toString()); // If palindrome // append sum if (isPalindrome(s)) { sum += i; } } return sum;}// Driver codevar n = 1;var ans = getSum(n);document.write( ans + "<br>");</script> |
Output:
45
Time Complexity: O(n*log(n))
Auxiliary Space: O(1)
Efficient approach:
On carefully observing the sum of n digit palindrome a series is formed i.e 45, 495, 49500, 495000, 49500000, 495000000. Therefore, by deducing this to a mathematical formula, we get for n = 1 sum = 45 and for n > 1 put sum = (99/2)*10^n-1*10^(n-1)/2
Below is the implementation of the above approach:
C++
// C++ program for// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate// sum of n digit numberlong double getSum(int n){ long double sum = 0; // Corner case if (n == 1) { sum = 45.0; } // Using above approach else { sum = (99.0 / 2.0) * pow(10, n - 1) * pow(10, (n - 1) / 2); } return sum;}// Driver codeint main(){ int n = 3; long double ans = getSum(n); cout << setprecision(12) << ans << '\n'; return 0;} |
Java
// Java program for// the above approachclass GFG{ // Function to calculate // sum of n digit number static double getSum(int n) { double sum = 0; // Corner case if (n == 1) { sum = 45.0; } // Using above approach else { sum = (99.0 / 2.0) * Math.pow(10, n - 1) * Math.pow(10, (n - 1) / 2); } return sum; } // Driver code public static void main(String[] args) { int n = 3; double ans = getSum(n); System.out.print(ans); }}// This code is contributed by PrinciRaj1992 |
Python3
# Python program for# the above approach# Function to calculate# sum of n digit numberdef getSum(n): sum = 0; # Corner case if (n == 1): sum = 45.0; # Using above approach else: sum = (99.0 / 2.0) * pow(10, n - 1)\ * pow(10, (n - 1) / 2); return sum;# Driver codeif __name__ == '__main__': n = 3; ans = int(getSum(n)); print(ans);# This code is contributed by 29AjayKumar |
C#
// C# program for// the above approachusing System;class GFG{ // Function to calculate // sum of n digit number static double getSum(int n) { double sum = 0; // Corner case if (n == 1) { sum = 45.0; } // Using above approach else { sum = (99.0 / 2.0) * Math.Pow(10, n - 1) * Math.Pow(10, (n - 1) / 2); } return sum; } // Driver code public static void Main(String[] args) { int n = 3; double ans = getSum(n); Console.Write(ans); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for// the above approach// Function to calculate// sum of n digit numberfunction getSum(n){ var sum = 0; // Corner case if (n == 1) { sum = 45.0; } // Using above approach else { sum = (99.0 / 2.0) * Math.pow(10, n - 1) * Math.pow(10, parseInt((n - 1) / 2)); } return sum;}// Driver codevar n = 3;var ans = getSum(n);document.write(ans + "<br>");</script> |
Output:
49500
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
