The Artima Developer Community
Sponsored Link

Java Answers Forum
Palindrome Problem

16 replies on 2 pages. Most recent reply: Nov 9, 2006 6:59 PM by Matt Gerrans

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 16 replies on 2 pages [ 1 2 | » ]
Ashish K

Posts: 2
Nickname: ksystech
Registered: Oct, 2006

Palindrome Problem Posted: Oct 11, 2006 3:37 AM
Reply to this message Reply
Advertisement
I am having some problem in compiling the code for the following problem....can anybody provide an alternative code for it...

Problem:-
A palindrome is a number such that when all its digits are reversed it is still the same as the original number. For example, the number 7007 is a palindrome. Reversing all its digits will give 7007 which is the same as the original number. Also, 997 is not a palindrome as reversing its digits gives 799 which is not the same as 997.

This problem is to do with palindromes but with a small twist. Find all the 3 and 4-digit positive integers that do not become a palindrome even after the following steps are repeated up to a 10,000 times. To understand the following steps better let us take a 4-digit positive integer, 4824 as an example.

1. Reverse the original number. Reversing 4824 yields 4284.
2. Add the original number and the reversed number. Adding 4824 to 4284 yields 9108.
3. Check if the new number is a palindrome. The reverse of 9108 is 8019 which is not the same as 9108. Hence 9108 is not a palindrome.
4. If the new number is not a palindrome replace the original number with the new number and repeat steps 1 through 4. In this case we replace 4824 with 9108 and repeat the steps all over again.

One iteration is counted as a single pass through all the four above steps.

Consider another example with a four digit positive integer 5689.

Iteration 1: Number: 5689, Reverse: 9865, Sum: 15554, Reverse: 45551
Iteration 2: Number: 15554, Reverse: 45551, Sum: 61105, Reverse: 50116
Iteration 3: Number: 61105, Reverse: 50116, Sum: 111221, Reverse: 122111
Iteration 4: Number: 111221, Reverse: 122111, Sum: 233332, Reverse: 233332

As per the above algorithm 5689 becomes a Palindrome in 4 iterations. The number 9999 for example does not throw up a palindrome even after 10 iterations.


Matthias Neumair

Posts: 660
Nickname: neumi
Registered: Sep, 2003

Re: Palindrome Problem Posted: Oct 12, 2006 12:58 AM
Reply to this message Reply
An alternative to what exactly?

We don't do other peoples homework here.

So post your code, tell us where your problems lie and we'll help you.

One hint:
For inverting the number try using the MOD operator (%) for getting the last digit and the DIV operator (/) to get the other digits.

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Palindrome Problem Posted: Oct 13, 2006 9:46 PM
Reply to this message Reply
Yeah, right. Let's see the code you are having trouble trying to compile, please.

Ashish K

Posts: 2
Nickname: ksystech
Registered: Oct, 2006

Re: Palindrome Problem Posted: Oct 15, 2006 8:33 PM
Reply to this message Reply
Hello...well I have been able to solve the 'out of memory' error wth the following code but now the problem is that I am unable to send inputs to the BigInteger...I dont knw how to give inputs to the BigInteger....I have to check for all 3 and 4 digit numbers...also I have to count the number of iterations after which a number becomes a palindrome...

The Code is:-
import java.math.BigInteger;

public class Palindrome1
{

public static boolean verbose = true;

public static void main(String[] args)
{
BigInteger l = new BigInteger("9867");
try
{
if (l.compareTo(BigInteger.ZERO) < 0)
{
System.err.println(l+ " -> TOO SMALL");
//continue;
}
System.out.println(l+ "->" + findPalindrome(l));
}
catch (NumberFormatException e)
{
System.err.println(l+ "-> INVALID");
}
catch (IllegalStateException e)
{
System.err.println(l+ "-> " + e);
}

}


public static BigInteger findPalindrome(BigInteger num)
{

if (num.compareTo(BigInteger.ZERO) < 0)
throw new IllegalStateException("negative");
if (isPalindrome(num))
return num;
return findPalindrome(num.add(reverseNumber(num)));
}

/** A large number */
protected static final int MAX_DIGITS = 1000;

/** Check if a number is palindromic. */
public static boolean isPalindrome(BigInteger num)
{
String digits = num.toString();
int numDigits = digits.length();
if (numDigits >= MAX_DIGITS)
{
throw new IllegalStateException("too big,can't be a palindrome");
}
// Consider any single digit to be as palindromic as can be
if (numDigits == 1)
return true;
for (int i=0; i<numDigits/2; i++)
{
if (digits.charAt(i) != digits.charAt(numDigits - i - 1))
return false;
}
return true;
}

static BigInteger reverseNumber(BigInteger num)
{
String digits = num.toString();
int numDigits = digits.length();
char[] sb = new char[numDigits];
for (int i=0; i<digits.length(); i++)
{
sb = digits.charAt(numDigits - i - 1);
}
return new BigInteger(new String(sb));
}
}



Please suggest proper changes or an alternative way to approach the problem...

Matthias Neumair

Posts: 660
Nickname: neumi
Registered: Sep, 2003

Re: Palindrome Problem Posted: Oct 16, 2006 4:06 AM
Reply to this message Reply
Fist of all, please use the java tags if you post code.
1. the code is easier to read then
2. you won't get the problem, that if you use i or b as an index it will be kicked out of the code and changes only the apperance of you code.

In my opinion there is a more elegant way to invert the digits in an integer number:

    private static int invertDigits(long number) {
        long newNumber = 0;
        //You can here do something to make sure 'number' is not negative
        while (number >= 0) {
            newNumber = newNumber * 10 + number %10;
            number = number / 10;
        }
        return newNumber;
    }


Now you just have to compare the numbers and in case they don't fit call your isPalindrome method again with the sum of the numbers.

btw: Why do you use BigInteger?

Matthias Neumair

Posts: 660
Nickname: neumi
Registered: Sep, 2003

Re: Palindrome Problem Posted: Oct 16, 2006 4:11 AM
Reply to this message Reply
Made a mistake:

I used the comparishion number >= 0

That will result in an endless loop. => Bad idea.

This is the correct comparison: number > 0

Matthias Neumair

Posts: 660
Nickname: neumi
Registered: Sep, 2003

Re: Palindrome Problem Posted: Oct 18, 2006 4:43 AM
Reply to this message Reply
I found another error. The return type of the method must be long.

So, here's the corrected code:

    private static long invertDigits(long myNumber) {
        //You can here do something to make sure 'number' is not negative
//    	if (myNumber < 0) {
//    	    return -invertDigits(-myNumber);
//    	}
        long newNumber = 0;
        while (myNumber > 0) {
            newNumber = newNumber * 10 + myNumber %10;
            myNumber = myNumber / 10;
        }
        return newNumber;
    }

fatih karakurt

Posts: 3
Nickname: karakfa
Registered: Oct, 2003

Re: Palindrome Problem Posted: Oct 18, 2006 6:32 AM
Reply to this message Reply
long type is not safe for this problem.
hint: 1495

Also there are easier ways to reverse a number if you think it as a String.
hint: StringBuffer

Quote: give someone a fish... / teach them to fish ...

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Palindrome Problem Posted: Oct 19, 2006 11:51 AM
Reply to this message Reply
Yeah, the StringBuffer solution is in an old thread in this same forum. This is a recycled and updated homework assignment.

By the way, I don't think using real number types works well for reversing numbers that end with 0s.

Matthias Neumair

Posts: 660
Nickname: neumi
Registered: Sep, 2003

Re: Palindrome Problem Posted: Oct 19, 2006 10:42 PM
Reply to this message Reply
Interesting point.
CAN a number with a 0 on the end be a palindrome?

Reveersing the String representation of a number is obviously not the same as reversing the number.

Have to look into the definition of palindrome, but I don't think that reverse(reverse(number)) == number is the condition.

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Palindrome Problem Posted: Oct 21, 2006 11:37 AM
Reply to this message Reply
Seems like for traditional (string) palidromes like "Madam I'm Adam" spaces and case are ignored, but otherwise
input == reverse(reverse(input))
I guess with number palidromes it is just a matter of whether you also throw out zeros.

Matthias Neumair

Posts: 660
Nickname: neumi
Registered: Sep, 2003

Re: Palindrome Problem Posted: Oct 23, 2006 5:37 AM
Reply to this message Reply
Well, I thought a palindrome referred to numbers, not to Strings. My fault.

SRV001

Posts: 13
Nickname: srv001
Registered: May, 2004

Re: Palindrome Problem Posted: Nov 7, 2006 5:27 AM
Reply to this message Reply
This was a great problem to use recursion. Here's how I did it:


public class Palindrome
{
private int iteration = 0;

private void calculatePalindrome(int number)
{
try {
int reverse = reverse(number);

if (number == reverse)
{
System.out.println(
"\nPalindrome found: [number = " + number
+ "] & [reverse = " + reverse + "]\n");
}
else
{
System.out.println(
"Iteration " + ++iteration
+ ": Number: " + number + ", Reverse: " + reverse
+ ", Sum: " + (number + reverse) + ", Reverse: " + reverse(number + reverse));

calculatePalindrome(number + reverse);
}
} catch (Exception e) {

}
}

private int reverse(int num)
{
int x,y,z = 0;
x = num;

while (x > 0)
{
y = x % 10;
x = x / 10;
z = 10 * z + y;
}

return z;
}

public static void main(String[] args)
{
Palindrome p = new Palindrome();
p.calculatePalindrome(1535);
}
}

Matthias Neumair

Posts: 660
Nickname: neumi
Registered: Sep, 2003

Re: Palindrome Problem Posted: Nov 7, 2006 10:46 PM
Reply to this message Reply
Well, you made the same error reversing the number as I did, you just made it worse.
int is even less useful then long.

1. This palindrome operation can generate VERY large numbers. If long is not able to store them, int certainly isn't.

2. They want to o this on a text base. Meaning:
reverse("0001234") == "4321000"
Your (and my) method would generate this:
reverse(0001234) == 4321

The recursion of the find palindrome method is rather easy.

I think the idea behind our versions is the same. Here's the code I came up with doing this during break time:
public class PalindromeFinder {
    /** inverts the decimal digits of a long value. myNumber must be bigger or equal 0
     * @param myNumer The number to be inverted
     * @return A number with the digits in reverse order
     */
    private static long invertDigits(long myNumber) {
        long newNumber = 0;
        while (myNumber > 0) {
            newNumber = newNumber * 10 + myNumber % 10;
            myNumber = myNumber / 10;
        }
        return newNumber;
    }
 
    /** Searches for a palindrome. Increments myNumber by invertDigits(myNumber) if myNumber is not a palindrome until the resulting value is a palindrome
     * @param myNumber The value for whom a palindrome is to be found. if (myNumber < 0) the result will be -searchForPalindrome(-myNumber)
     * @return The palindrome of the number.
     */
    public static long searchForPalindrome(long myNumber) {
        if (myNumber < 0)
            return -searchForPalindrome(-myNumber);
        long invertedNumber = 0;
        int counter = 0;
        do {
            myNumber+=invertedNumber;
            invertedNumber = invertDigits(myNumber);
            counter ++;
        } while (invertedNumber != myNumber);
        System.out.print(counter);
        return myNumber;
    }
 
    /** inverts the decimal digits of a long value. myNumber must be bigger or equal 0
     * @param myNumer The number to be inverted
     * @param divisor must in [2, 10]
     * @return A number with the digits in reverse order
     */
    private static long invertDigits(long myNumber, int divisor) {
        long newNumber = 0;
        while (myNumber > 0) {
            newNumber = newNumber * divisor + myNumber % divisor;
            myNumber = myNumber / divisor;
        }
        return newNumber;
    }
 
    public static void main(String[] args) {
//	System.out.println(invertDigits(415,8));
    	long[] myNumbers = new long[]{1495, 919, 1234, 415, 71247, 2572, 7257, -8316717, 512479};
    	for (long myNumber : myNumbers) {
	        System.out.print("Palindrome for " + myNumber + " after ");
	        long palindrome = searchForPalindrome(myNumber);
	        System.out.println(" step(s) is " + palindrome);
    	}
    }
}


You can use this code also to invert the digits of a number based on the octal system or any system based on a number from 2 up to 10.
There's no error handling for numbers which can't have a palindrome. One possibility would be to abort after a certain number of steps.

Matt Gerrans

Posts: 1153
Nickname: matt
Registered: Feb, 2002

Re: Palindrome Problem Posted: Nov 8, 2006 9:41 AM
Reply to this message Reply
> Well, you made the same error reversing the number as I
> did, you just made it worse.


You guys might want to consider a little unit testing before posting code to public forums. ;)

Flat View: This topic has 16 replies on 2 pages [ 1  2 | » ]
Topic: Palindrome Problem Previous Topic   Next Topic Topic: How to come out from frame

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use