Please navigate to the bottom of the page for Table of Contents

Saturday, May 14, 2011

How to find if a number is a Palindrome?

Read the question. Listen very carefully to the question. Each word may have a meaning. In my experience, I have seen many interviewees just hear the last word: palindrome. Then I start getting solutions and examples of palindrome words. But note the question: It says a number. String operations are way more costly than number crunching.
Let's now dive into some possible solutions for this problem.
public static bool IsPalindrome(long number)
{
bool isPalin = true;

// inefficient solution - convert number to string
string numAsStr = number.ToString();

// more inefficiency - looping through the entire string
// could have achieved the same by traversing just half the string
for (int i = 0, j = numAsStr.Length - 1; i < numAsStr.Length - 1; i++, j--)
{
if (numAsStr[i] != numAsStr[j])
{
// the corresponding locations do not match
isPalin = false;
// some people forget to break out of the loop
// extremely bad - no need to do any further comparisons
break;
}
}
return isPalin;
}


The above solution was an in-efficient solution. It works, but does not get you any points. So, now let's see what improvements can be made to the above program.

public static bool IsPalindrome2(long number)
{
bool isPalin = true;

// inefficient solution - convert number to string
string numAsStr = number.ToString();

// we can find if a string is palindrome or not by just traversing half the string
for (int i = 0, j = numAsStr.Length - 1; i < (numAsStr.Length) / 2; i++, j--)
{
if (numAsStr[i] != numAsStr[j])
{
// the corresponding locations do not match
isPalin = false;
// some people forget to break out of the loop
// extremely bad - no need to do any further comparisons
break;
}
}
return isPalin;
}


In the above solution, we cut our execution time by almost half. Better, but not good enough. At this point, the interviewer should have a pretty good idea of your skills on reviewing code and making changes to improve it. Let's assume that he still wants you to keep digging.



public static bool IsPalindrome3(long number)
{
// since the input is a number, one very fast way way would be 
// to reverse the number and compare to original
long revNum = ReverseNumber(number);

return (number == revNum);
}

private static long ReverseNumber(long number)
{
long retVal = 0;
do
{
// get the last digit by using the modulo (remainder) operator
retVal = (retVal * 10) + (number % 10);
// drop the last digit from the number
number = number / 10;
}
while (number != 0);
return retVal;
}




If you run some performance tests with larges number sets on the above solutions, you will find that the 3rd solution is the most performant. I hope this example has shown you one way to attempt to solve a coding question. Remember, it is not just about the answer. The interviewer is trying to find your ability to think, debug and troubleshoot a problem.

21 comments:

  1. Great example!

    More examples of programming elegance please :)

    ReplyDelete
  2. class Palindrome
    {
    static void Main()
    {
    string checkStr, sampleStr;
    char[] temp;

    System.Console.Write("Enter your String: ");

    sampleStr = System.Console.ReadLine();

    checkStr = sampleStr.Replace(" ", "");

    checkStr = checkStr.ToLower();

    temp = checkStr.ToCharArray();

    System.Array.Reverse(temp);

    if(checkStr== new string(temp))
    {
    System.Console.WriteLine(""{0}" is a palindrome.",sampleStr);
    }

    else
    {
    System.Console.WriteLine(""{0}" is NOT a palindrome.",sampleStr);
    }

    }
    }

    ReplyDelete
    Replies
    1. gayathri,
      The goal of this exercise is to not use built-in functions. You need to show that you understand how the system works underneath and that you can get the best performance possible.

      Delete
    2. if(sampleStr==new String(temp)),correct it ;-)

      Delete
  3. Great collection of questions in one plate!

    ReplyDelete
  4. The last solution is so smart :)

    ReplyDelete
  5. class Program
    {
    static void Main(string[] args)
    {
    Console.WriteLine("enter string");
    string name = Console.ReadLine();
    Boolean palindrome =false;
    int len = name.Length;
    for (int i = 0; i < (len - 1); i++)
    {
    if (name[i] == name[len - 1])
    {
    palindrome = true;
    i++;
    }
    else
    {
    break;

    }
    }
    if (palindrome == true)
    {
    Console.WriteLine(" ur name is palindrome");
    Console.ReadKey();
    }
    else
    {
    Console.WriteLine(" ur name is not a palindrome");
    Console.ReadKey();
    }
    }
    }

    ReplyDelete
    Replies
    1. Vivek,
      Take a look at the third solution in my post. Why would you want to traverse the entire length of the string when in fact you can get the answer in half?

      Delete
    2. Vivek,
      just change insted of i++; write len--; and else past write palindrome=false;
      then u r code is working fine

      Delete
  6. Let me try this one in ruby:

    def palindrome?(n)
    digits = Math.log10(n).to_i + 1
    (digits/2).times do |right|
    left = digits-1-right
    if n/(10*left)%10 != n/(10*right)%10
    return false
    end
    end
    return true
    end

    Btw, I can't seem to post in safari, but works in chrome....

    ReplyDelete
  7. @Nikhil Singhal :

    I tried the second example you gave in your post above which traverse only half the string. But i think its wrong. because when the user enters a number such as "4254", the variable "isPalin" is considered true, and the for loop breaks out after the firs iteration as numtoStr[0] = 4 and numtoStr[3]=4

    ReplyDelete
    Replies
    1. Imad,
      The loop will execute 2 times as length/2 is 4/2 = 2 and the counter starts at 0. So, in two iterations, the string will be reversed. I would strongly recommend that you type this code in a program and execute it step by step.

      Delete
  8. ReverseNumber function doesn't work for numbers that end in zero. For example try 120 and it returns 21

    ReplyDelete
  9. haha. Never mind. Duh, 120 reversed is actually 21!! Sorry. Thanks for this great blog and articles. This is helping me a lot!

    ReplyDelete
  10. Good explanation .. Thanks for the post...

    ReplyDelete
  11. What would your impression be of this approach?

    private static bool isPalidrome(int num)
    {
    return num.ToString() == new string(num.ToString().Reverse().ToArray());
    }

    ReplyDelete
    Replies
    1. Sure. It would work. But think about the performance implications of your code. What if the string is a million characters long? What complexity and memory pressure are you adding?

      Delete
  12. Here is the algo to check number is palindrome or not
    1. Reverse the digits of inputNumber, and store it in another integer variable(Let's call it reverseNumber).
    2. Compare inputNumber and reverseNumber.
    http://www.techcrashcourse.com/2014/10/c-program-check-palindrome-number.html

    ReplyDelete
  13. I have an doubt I'm new to c# can I just know to call this method in main method .I don't know how to do that

    ReplyDelete
  14. using System;
    namespace palindrome
    {
    class Program
    {
    static void Main(string[] args)
    {
    string s,revs="";
    Console.WriteLine(" Enter string");
    s = Console.ReadLine();
    for (int i = s.Length-1; i >=0; i--) //String Reverse
    {
    revs += s[i].ToString();
    }
    if (revs == s) // Checking whether string is palindrome or not
    {
    Console.WriteLine("String is Palindrome \n Entered String Was {0} and reverse string is {1}", s, revs);
    }
    else
    {
    Console.WriteLine("String is not Palindrome \n Entered String Was {0} and reverse string is {1}", s, revs);
    }
    Console.ReadKey();
    Console.Readline();
    }
    }
    }

    ReplyDelete