Double Base Palindrome In C++

In this article, we will discuss the Double Base Palindrome in C++ with their, example, time complexity, and space complexity.

Double Base Palindrome:

A sequence of characters or numbers that read the same both forward and backward is called a palindrome . In base 10, for instance, the number 121 is a palindrome since it gives the same result when read from left to right or right to left. A number must meet the palindromic criteria in both base 10 and another base k to be regarded as a double base palindrome.

Example-1: 10 2

Numbers less than 10 that are palindromes in both base 10 and base 2: 1, 3, 5, 7, 9.

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

Example- 2: 100 2

Numbers less than 100 that are palindromes in both base 10 and base 2: 1, 3, 5, 7, 9, 33, 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 us take an example to illustrate the Double Base Palindrome in C++

Example


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

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++ program determines the sum of numbers that are palindromes in both base 10 and a specified base k and are less than a given integer n. By flipping the digits of a number, the isPalindrome function determines whether it is a palindrome in base 10. The function isPalindromeInBaseK retains the number's digits, transforms it to base k, and determines whether or not they form a palindrome. Every integer between 1 and n-1 is iterated through the findSum method, which sums the numbers that meet both palindrome requirements. After receiving n and k as inputs, the main function calls findSum and outputs the outcome. By using this method, the sum will only contain numbers that meet both palindrome requirements.