We’ll start by finding the reverse of a number. We’ll then use the reverse() function to determine whether a number is a palindrome or not and determine the binary representation of a decimal number.

Reverse of a number

Write a function that takes an input integer from the user and returns the reverse of it.

Sample input

Passed parameter: 12345

Sample output

Returned value: 54321

Here’s the prototype of the required function:

int reverse(int num);

How can we construct a new number which is the reversal of num?

Idea: Reverse of a number

'Chop the number digit by digit from the rightmost position of num and keep appending it to the right of the constructed new number m.

Implementation

Here are the further implementation details:

  1. To get the last digit of num, we’ill take the modulus of the num by 10. For example if num has 12345 then num%10 will give us 5. We can store that as a rem.
   rem = num % 10; // rem = 5
  1. Now, we want to store the reverse of num in m, which is initially zero. We’ll multiply m with 10 and add rem in m.
m = (m*10)+rem; //m = 5 (0x10+5)
  1. We have 5 in the m variable. In the next iteration, we need 1234 instead of 12345, so we’ll divide num by 10.
num = num / 10; // Now we have num = 1234 (12345/10)
  1. We’ll repeat all these steps until num equals 0. We’ll do this in a function and we will call it reverse().

Let’s write the complete code and see the output:

#include <iostream>
using namespace std;
//this function returns the reverse of number
int reverse(int num);   //prototype
int main()
{
    int num;
    cout << "Enter the number: ";
    cin >> num;
    cout << "The reverse is: " << reverse(num) << endl;
    return 0;
}
int reverse(int num)    //function
{
    int rem, m=0;
    while(num!=0)
    {
        rem=num%10; // last digit
        m=(m*10)+rem; //concatenate number
        num=num/10; // shrink the number
    }
    return m;
}
Finding the reverse of a number

Using the reverse() function

We can use the reverse() function to solve multiple problems. Here, we’ll use this function to solve the following two problems:

  1. Palindrome number
  2. Decimal to binary

Let’s first discuss the palindrome number.

Palindrome number

A palindrome is a number, word, or sequence of characters that reads the same forward and backward.

For example, we have the number 121, which reads the same forward or backward. In the same way, if we reverse the number 123, its reverse will be 321, which is not the same. Hence this is not a palindrome.

Idea: Palindrome number

In the palindrome number problem, we call the reverse() function to check whether the reverse of the number is equal to the actual number. If the actual number is equal to the reverse of the number, we can say this is a palindrome.

Sample program

12321
It is a palindrome.

Instruction: Write the implementation for the isPalindrome() function and the reverse() function, which you may want to use inside the isPalindrome() function.

If you need a hint, click the Show Hint button below.

Playground: Palindrome number

Add your code in the code editor below:

#include <iostream>
using namespace std;
//This function returns the reverse of a number
int reverse(int num);   
//This function tells if the number is palindrome or not
bool isPalindrome(int num);  
int main()
{
    int num;
    cin >> num; 
    cout << "Enter the number to check if its a palindrome or not: \n";

    if(isPalindrome(num))
    {
        cout << num << " is a palindrome." << endl;
    }
    else
        cout << num << " is not a palindrome." << endl;
}
int reverse(int num)    //reverse function
{
    // Write your code
}
bool isPalindrome(int num)    //palindrome function
{
    // Write your code
}
Finding if a number is a palindrome

Now, let’s look at another example that uses the reverse() function.

Decimal to binary

Write a function that takes a decimal number and returns its binary representation.

Sample input

10

Sample output

1010

Decimal to binary, base 2 (or any base b≤10b \leq 10 )

  1. We divide the number by 2 (or any base bb) until the number is equal to 0.
  2. Remainder of the number in each step will give either a 0 or a 1 (0, to b−1b-1). Keep writing it along every division step.
  3. Append the remainder of each step from bottom to top.

Let’s see the animation of decimal to binary conversion:

Playground exercise: Binary to decimal

There are multiple implementation versions to convert the decimal to a binary number.

Instruction: Go through each implementation version and write its respective code inside the respective function name in the code editor below. In the end, test all the codes and execute them step by step.

We have already included the reverse() function so you can call it directly wherever needed.

#include <iostream>
using namespace std;
#include<cmath> // cmath library contains the pow() function 

int reverse(int num);

int decimalToBinaryV1(int n)  // with a logical error
{
    // Paste the code of v1
    return 0;
}
int decimalToBinaryV2(int n)  // with a logical error
{
    // Paste the code of v2
    return 0;
}
int decimalToBinaryV3(int n)  // with a logical error
{
    // Paste the code of v3
    return 0;
}
int decimalToBinaryV4(int n)  // with a logical error
{
    // Paste the code of v4
    return 0;
}
int main()
{
    // Uncomment the function that you want to test
    //cout<<decimalToBinaryV1(24)<<endl; 
    //cout<<decimalToBinaryV2(24)<<endl; 
    //cout<<decimalToBinaryV3(24)<<endl; 
    //cout<<decimalToBinaryV4(24)<<endl; 
    return 0;
}
Finding the binary representation of a number

Implementation 1: Decimal to binary

Let’s discuss the program logic in which w’ll do the following steps:

  1. We have two variables, rem (to store the remainder of each step) and ans (to append the binary numbers).
  2. We’ll make a loop in which we can divide the number by 2 until the number is equal to 0.
  3. In each iteration of the loop, w’ill do the following:
    ans = ans*10+rem; // it will 
append the binary numbers
  4. As we saw in the above animation, we append the remainder of each step from bottom to top. However, here we are appending the remainder of each step in ans from top to bottom which is a problem.
  5. To solve this problem we can reverse the binary number in the end. The reverse() function will reverse the ans.

Let’s see the animation below regarding the above logic:

Let’s write a function for the above discussion:

Press + to interact
int decimalToBinaryV1(int n)  
{
    int ans = 0, rem;
    while(n!=0)
    {
        rem = n%2;            // remainder of number store in rem
        ans = ans*10 +       // shifting 1 to the left
                      rem;   // concatenation of remainder
        
        n = n/2;             // divide the number by 2 
    }
    
    return reverse(ans);     //reverse the number
}

Instruction: Please copy the decimalToBinaryV1() function and paste it into the above playground and execute it step by step.

Let’s execute the decimalToBinaryV1() function by passing 24 and see the output. Is there any logical mistake in this function?

1

What is the binary number of 24?

A)

11000

B)

11

Question 1 of 20 attempted

11000 is the binary of 24 but in the above program, it stores only 11 and skips the last three zeros. How can we fix it?

Implementation: 2 Fixing the zeros

If you dry-run the above implementation 1 on input 36, which has the binary of 10100, our program will show 101

Instruction: Try it yourself in the playground.

This shows we don’t need to worry about the zeros which appear between 1’s. The only issue is the trailing zeroes which appear in the beginning as remainders.

So here is the idea:

  1. We need to count the initial zeros before 1. So we need two variables, initialZeroesCount (type integer) to count the initial zeroes and initialZeroesFinished which is the bool type to maintain whether initial zeroes are finished or not.

  2. We will compute ans, as it is mentioned in implementation 1.

    • Steps 1 and 2 are repeated until num is shrunk to 0.

  3. To append the initial zeros in binary digits we will multiply the reversed value, ans, with 10 in a loop that will iterate from 1 until initialZeroesCount.

Let’s modify the above function and see the changes we have highlighted:

Press + to interact
int decimalToBinaryV2(int n)  
{
    int ans = 0, rem;
    int initialZeroesCount=0;
    bool initialZeroesFinished = false;
    while(n!=0)
    {
        rem = n%2;
        if(!initialZeroesFinished)
        {
            if(rem==0)
                initialZeroesCount++;
            else
                initialZeroesFinished = true;
        }
        ans = ans*10 +       // shifting 1 to the left
                      rem;   // concatenation of remainder
        
        n = n/2;
    }
    
    ans = reverse(ans);
    for(int i=1; i<=initialZeroesCount; i++)
        ans = ans*10;       //To add the zeroes in binary number
    
    return ans;
}

Instruction: Please copy the above function and paste it into the above playground and execute it step by step.

Implementation 3: Using power function

We have another method to solve this problem without the reverse() function. W’ll use the pow() function (included in the cmath library) in which we will use base 10 and in each iteration of the loop we will increment in power by 1. First, have a look at the following animation:

Did you see how we appended the binary number to the left in the above animation? So we’ll do some changes in the above function:

Press + to interact
int decimalToBinaryV3(int n)  
{
    int ans = 0, rem;
    int shifter=0;
    while(n!=0)
    {
        rem = n%2;
        // Now we want to concatenate rem to the right of ans
        ans = ans +        
                    rem * pow(10, shifter);  // 0+ 0x10^0 -> 0+ 0x10^1 -> ...
        shifter++; //increment in power
        n=n/2;
    }
    return ans;
}

Instruction: Please copy the above function and paste it into the above playground and execute it step by step.

Implementation 4: Avoiding recomputing power

We’ll discuss one elegent elegant solution without the pow() function. W’ll do some changings in the above function and perform the following steps:

For example, we have a number = 10 and want to convert it into binary.

  1. To get a remainder of the n we will take a modulus with 2.
rem = n%2; // rem = 0 (10 % 2 = 0)
  1. Now, we want to append the binary numbers to the left direction. We’ll multiply powerfactor (initially powerfactor=1) with rem and add into ans to store the binary.
ans = ans + 
                    rem * powerfactor; // ans = 0 + (0 x 1)
  1. We’ll multiply powerfactor with 10 in each iteration of loop.
powerfactor = powerfactor*10; // powerfactor = 1 x 10
  1. Now, we’ll divide n with 2 that return us 5 in the first iteration.
n =n/2; // n = 10/2;

We’ll repeat each step until the number is equal to 0 in the while loop. In the end, w’ll return the ans.

Let’s write a complete code below and see the output:

Press + to interact
int decimalToBinaryV4(int n)  
{
    int ans = 0, rem;
    int powerfactor=1;
    while(n!=0)
    {
        rem = n%2;
        // Now we want to concatenate rem to the right of ans
        
        ans = ans + 
                    rem * powerfactor;
                    
        powerfactor = powerfactor*10; 
        n=n/2;
    }
    return ans;
}

Instruction: Please copy the above function and paste it into the above playground and execute it step by step.

Exercise: Decimal to base bb

Convert the above program with base 10 to any base b≤9b\leq 9.