Solving the 'Palindrome Number' Puzzle in C

Introduction

As a break from my usual posts, I thought I might actually try to program in C, for once.

In this post, I'll be sharing my thought processes and a solution to an online puzzle. Feel free to give the problem a try yourself!

Problem Statement

Write a function that returns true if a number x is a palindrome, and false otherwise.

Process

It's always best to break down a larger problem into more manageable chunks. This can be done most easily using comments.

bool isPalindrome(int x)
{
	// reverse the number
		// loop over digits of x
		// gather the remainder
		// keep adding remainder to a variable, 
		// multiplying by 10 each iteration

	// compare the reversed number with the original
}

With a basic idea in mind, we can start coding.

bool isPalindrome(int x)
{
	// reverse the number

	int rev = 0;
	// we need og value of x, create a copy
	int x2 = x;
	// loops over digits of x
	while (x2 != 0)
	{
		// multiplies old value of rev by 10 and adds remainder
		// to ensure that number is reversed, not replicated
		rev = (rev * 10) + (x2 % 10);
		// "cuts off" last digit
		x2 /= 10;
	}
	
	// compare the reversed number with the original

	return x == rev;
}

So, fingers crossed, this should work...

It seems like our code doesn't work with negative numbers, and that somewhat makes sense. The reversed form of -121 is 121-, which isn't even a valid number.

Therefore, we can safely say that any number less than 0 should result in false:

bool isPalindrome(int x)
{
	// negative number palindromes don't exist
	if (x < 0)
		return false;

	// reverse the number

	int rev = 0;
	// we need og value of x, create a copy
	int x2 = x;
	// loops over digits of x
	while (x2 != 0)
	{
		// multiplies old value of rev by 10 and adds remainder
		// to ensure that number is reversed, not replicated
		rev = (rev * 10) + (x2 % 10);
		// "cuts off" last digit
		x2 /= 10;
	}
	
	// compare the reversed number with the original

	return x == rev;
}

Let's try checking again.

It seems like we've hit another snag in our program, having only passed 30/11511 test cases.

Taking a closer look at the error message, "998765432 * 10 cannot be represented in type 'int'." That number just so happens to be the reversed form of x... so we know we did something right, at least.

The issue lies with the amount of digits an int can store with 32 bits: 2^31 - 1.

When we reversed the number, this max value was exceeded. Luckily, there's a simple fix to this bug:

bool isPalindrome(int x)
{
	// negative number palindromes don't exist
	if (x < 0)
		return false;

	// reverse the number

	int rev = 0;
	// we need og value of x, create a copy
	int x2 = x;
	// loops over digits of x
	while (x2 != 0)
	{
		// checks that rev * 10 doesn't exceed or fall below
		// the max and min int values
		if (rev * 10 > INT_MAX || rev * 10 < INT_MIN)
			return false;
		// multiplies old value of rev by 10 and adds remainder
		// to ensure that number is reversed, not replicated
		rev = (rev * 10) + (x2 % 10);
		// "cuts off" last digit
		x2 /= 10;
	}
	
	// compares the reversed number with the original

	return x == rev;
}

Luckily, this time our program passed.

Final Thoughts

While this solution isn't necessarily the best time and space complexity-wise, at the very least, it works.

Hopefully this post was useful in one way or another. Thanks for reading!