Double Base Palindrome In C++

In this tutorial, we will explore the concept of Double Base Palindrome in C++, including an example, the time complexity analysis, and the space complexity evaluation.

Double Base Palindrome:

A string of characters or digits that remains identical when read forwards and backwards is known as a palindrome. For example, in the decimal system, the number 121 is a palindrome because it reads the same forwards and backwards. To qualify as a double base palindrome, a number must exhibit palindromic properties in both base 10 and another base, denoted as base k.

Example-1: 10 2

Numbers that are palindromes in both base 10 and binary for values under 10: 1, 3, 5, 7, 9.

Sum: 1 + 3 + 5 + 7 + 9 = 25.

Example- 2: 100 2

Numbers that are palindromic in both base 10 and base 2, and are less than 100: 1, 3, 5, 7, 9, 33, and 99.

Sum: 1 + 3 + 5 + 7 + 9 + 33 + 99 = 157.

Method-1:

• ✅ Determine whether the given number is a base-10 palindrome: The first step for every number less than n is to determine whether it is a base-10 palindrome. A number (such as 121 or 333) is a palindrome if it reads the same both forward and backward. One way to find out this is to reverse its digits and compare it to the original number.
• ✅ Convert the number to base k: The next step is to convert a number into base k if it is a palindrome in base 10. This involves repeatedly dividing the number by k and storing the remainder, which will represent the digits in the new base.
• ✅ Verify whether the given number is a base-k palindrome: Once the number has been converted to base k, see if the new base's digits create a palindrome. The digits from both ends (i.e., the first and last digits) can be compared to make sure they are the same.
• ✅ Add the number to the sum if both conditions are met: Include it in the running sum if the integer is a palindrome in both base 10 and base k. By using this step, the final sum will be sure to contain only numbers that meet both requirements.

Example:

Let's consider a scenario to demonstrate the concept of Double Base Palindrome in C++.

#include <iostream>
#include <vector>
#include <cmath>
// Function to check if a number is palindrome in base 10
bool isPalindrome(int num) 
{
    int original = num;
    int reversed = 0;
    while (num > 0)
    {
        int digit = num % 10;
        reversed = reversed * 10 + digit;
        num /= 10;
    }
    return original == reversed;
}
// Function to convert a number to base k and check if it's palindrome
bool isPalindromeInBaseK(int num, int k)
{
    std::vector<int> digits;
    // Convert the number to base k
    while (num > 0) 
    {
        digits.push_back(num % k);
        num /= k;
    }
    // Check if the digits array is a palindrome
    int left = 0, right = digits.size() - 1;
    while (left < right) 
    {
        if (digits[left] != digits[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
// Function to find the sum of all numbers less than n that are palindrome in both base 10 and base k
int findSum(int n, int k)
{
    int sum = 0;
    for (int i = 1; i < n; i++) 
    {
        if (isPalindrome(i) && isPalindromeInBaseK(i, k))
        {
            sum += i;
        }
    }
    return sum;
}
int main()
{
    int n, k;
    // Taking input for n and k
    std::cout << "Enter the value of n: ";
    std::cin >> n;
    std::cout << "Enter the base k: ";
    std::cin >> k;
    // Find the sum of numbers less than n that are palindrome in both base 10 and base k
    int result = findSum(n, k);
    // Output the result
    std::cout << "The sum of numbers that are palindrome in both base 10 and base " << k << " is: " << result << std::endl;
    return 0;
}

Output:

Enter the value of n: 100
Enter the base k: 2
The sum of numbers that are palindrome in both base 10 and base 2 is: 157

Complexity Analysis:

• ✅ Time Complexity: O(n*log(n))
• ✅ Auxiliary Space: O(log(n))

Explanation:

This C++ software calculates the total of numbers that exhibit palindromic characteristics in both the decimal base and a specified base k, all while staying below a designated integer n. The isPalindrome function assesses whether a number remains the same when its digits are reversed, thereby determining if it is a palindrome in base 10. On the other hand, the isPalindromeInBaseK function maintains the original digits of the number, converts it to base k, and verifies if it forms a palindrome in that base. The findSum method iterates over every integer from 1 to n-1, accumulating the numbers that fulfill both palindrome conditions. Upon receiving inputs n and k, the main function invokes findSum and displays the final result. This approach guarantees that the sum exclusively comprises numbers meeting the dual palindrome criteria.