How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the C++ programming language

Published on 7 June 2024 03:52 AM

How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the C++ programming language

Table of Contents

Problem Statement

It's permissible to assume the first two numbers and simply list them.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Find palindromic numbers in both binary and ternary bases step by step in the C++ programming language

This C++ program finds the first six numbers that are palindromic in both binary and ternary number systems. Here's a detailed explanation of the code:

  1. to_base_string Function:

    • This function converts a decimal number (number) to a string representing its value in the specified base.
    • It iteratively calculates the remainders when dividing the number by the base, converts them to characters, and appends them to a result string.
    • Finally, it reverses the result string and returns it.
  2. display Function:

    • This function displays the decimal representation of a number, its binary representation (base 2), and its ternary representation (base 3) on the console.
  3. is_palindromic Function:

    • This function checks if a given string (number) is a palindrome by comparing it with its reverse.
  4. create_ternary_palindrome Function:

    • This function creates a ternary palindrome whose left part is the ternary equivalent of the given number.
    • It first converts the number to a ternary string.
    • Then, it iteratively processes the ternary string from right to left, mirroring the digits to create the right part of the palindrome.
    • It adds a '1' as the middle digit and multiplies the given number by the appropriate power of 3 to create the left part.
    • Finally, it combines the left and right parts to form the ternary palindrome and returns it.
  5. main Function:

    • The program starts by displaying the first two numbers (0 and 1) which are palindromic in all three bases (decimal, binary, and ternary).
    • It initializes a loop that continues until six numbers have been found that satisfy the conditions.
    • Inside the loop:
      • It creates a ternary palindrome for the current number (number).
      • It checks if the ternary palindrome is odd (binary palindromes cannot be even).
      • If the ternary palindrome is odd, it converts it to binary and checks if its length is odd (odd-length binary strings can be palindromes).
      • If both conditions are met and the binary representation is palindromic, it displays the number and increments the count.
      • The loop continues until six such numbers are found.

Source code in the cpp programming language

#include <algorithm>
#include <cstdint>
#include <iostream>

// Convert the given decimal number to the given number base
// and return it converted to a string
std::string to_base_string(const uint64_t& number, const uint32_t& base) {
	uint64_t n = number;
	if ( n == 0 ) {
		return "0";
	}

	std::string result;
	while ( n > 0 ) {
		result += std::to_string(n % base);
		n /= base;
	}
	std::reverse(result.begin(), result.end());
	return result;
}

void display(const uint64_t& number) {
	std::cout << "Decimal: " << number << std::endl;
	std::cout << "Binary : " << to_base_string(number, 2) << std::endl;
	std::cout << "Ternary: " << to_base_string(number, 3) << std::endl << std::endl;
}

bool is_palindromic(const std::string& number) {
	std::string copy = number;
	std::reverse(copy.begin(), copy.end());
	return number == copy;
}

// Create a ternary palindrome whose left part is the ternary equivalent of the given number
// and return it converted to a decimal
uint64_t create_ternary_palindrome(const uint64_t& number) {
	std::string ternary = to_base_string(number, 3);
	uint64_t power_of_3 = 1;
	uint64_t result = 0;
	for ( uint64_t i = 0; i < ternary.length(); ++i ) { // Right part of palindrome is the mirror image of left part
		if ( ternary[i] > '0' ) {
			result += ( ternary[i] - '0' ) * power_of_3;
		}
		power_of_3 *= 3;
	}
	result += power_of_3; // Middle digit must be 1
	power_of_3 *= 3;
	result += number * power_of_3; // Left part is the given number multiplied by the appropriate power of 3
	return result;
}

int main() {
	std::cout << "The first 6 numbers which are palindromic in both binary and ternary are:" << std::endl;
	display(0); // 0 is a palindrome in all 3 bases
	display(1); // 1 is a palindrome in all 3 bases

	uint64_t number = 1;
	uint32_t count = 2;
	do {
		uint64_t ternary = create_ternary_palindrome(number);
		if ( ternary % 2 == 1 )  { // Cannot be an even number since its binary equivalent would end in zero
			std::string binary = to_base_string(ternary, 2);
			if ( binary.length() % 2 == 1 ) { // Binary palindrome must have an odd number of digits
				if ( is_palindromic(binary) ) {
					display(ternary);
					count++;
				}
			}
		}
		number++;
	}
	while ( count < 6 );
}


  

You may also check:How to resolve the algorithm Last Friday of each month step by step in the 360 Assembly programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Verilog programming language
You may also check:How to resolve the algorithm Exponentiation order step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Evaluate binomial coefficients step by step in the Racket programming language
You may also check:How to resolve the algorithm Chinese remainder theorem step by step in the Ruby programming language