10
\$\begingroup\$

Challenge:

Reverse the digits of a number and add it to the original until the number is a palindrome

Specifications:

Your program should accept as its first argument a path to a filename.
Each line in this file is one test case containing an integer n < 10,000.

Assume each test case will always have an answer and that it is computable with less than 100 iterations.

For each line of input, print a line of output containing the number of iterations to compute the palindrome and the resulting palindrome, on one line separated by a single space.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class ReverseAndAdd {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            findAndPrintPalindrome(input.nextLine());
        }
    }

    private static void findAndPrintPalindrome(String line){
        System.out.println(getPalindrome(line));
    }

    private static String getPalindrome(String line) {
        int reverseCount = 0,
            currentNum = Integer.parseInt(line)
        ;

        while (!isPalindromic(currentNum)) {
            currentNum += reverse(currentNum);
            reverseCount++;
        }

        return reverseCount + " " + currentNum;
    }

    private static boolean isPalindromic(int s) {
        return s == reverse(s);
    }

    private static int reverse(int n) {
        return Integer.parseInt(
            new StringBuilder(Integer.toString(n)).reverse().toString()
        );
    }
}

Sample Input:

8
125
195

Sample Output:

0 8
1 646
4 9339

I'm looking to pinpoint:

  1. Anything I could alter to optimize this program.
  2. General feedback on good vs poor practices in my code.
\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

reverse gets called twice in every step

In every step of the process to finding a palindromic number, the reverse method gets called twice:

    while (!isPalindromic(currentNum)) {
        currentNum += reverse(currentNum);
        reverseCount++;
    }

private static boolean isPalindromic(int s) {
    return s == reverse(s);
}

First it gets called in the while loop's condition statement, then again inside the loop body. This is a waste, it would be better to refactor to only call once per iteration.

Instead of reverseCount, the name stepCount would seem slightly more appropriate, but this may be just a matter of taste.

isPalindromic is simple but lazy

Although the implementation of isPalindromic is sweet and simple, it's wasteful and inaccurate.

It involves converting the number to String, reversing, and then converting back to integer. A more efficient way would be to compare the digits of position \$i\$ and \$n - i - 1\$, until you reach position \$n/2\$.

The method will not work with negative numbers because reverse will not work with negative numbers.

Here's an implementation using math, that works with negative numbers too:

private static boolean isPalindromic(int num) {
    int digits = (int) Math.log10(Math.abs(num)) + 1;
    int firstDivisor = (int) Math.pow(10, digits - 1);
    int lastDivisor = 1;
    while (firstDivisor > lastDivisor) {
        int firstDigit = num / firstDivisor % 10;
        int lastDigit = num / lastDivisor % 10;
        if (firstDigit != lastDigit) {
            return false;
        }
        firstDivisor /= 10;
        lastDivisor *= 10;
    }
    return true;
}

And some unit tests to go with it:

@Test
public void testPalindromic_3() {
    assertTrue(isPalindromic(3));
}

@Test
public void testPalindromic_13() {
    assertFalse(isPalindromic(13));
}

@Test
public void testPalindromic_22() {
    assertTrue(isPalindromic(22));
}

@Test
public void testPalindromic_333() {
    assertTrue(isPalindromic(333));
}

@Test
public void testPalindromic_1991() {
    assertTrue(isPalindromic(1991));
}

@Test
public void testPalindromic_334() {
    assertFalse(isPalindromic(334));
}

@Test
public void testPalindromic_minus12321() {
    assertTrue(isPalindromic(-12321));
}

reverse is simple but lazy

As mentioned above, the simple but lazy implementation breaks on negative numbers. It also breaks on numbers that cause integer overflow when reversed. And like with isPalindromic, the logic is wasteful. It would be better to implement this too using basic math logic:

private static int reverse(int num) {
    long reversed = 0;
    int work = num;
    while (work != 0) {
        reversed *= 10;
        reversed += work % 10;
        if (reversed > Integer.MAX_VALUE) {
            throw new IllegalArgumentException("Reversing this number will cause integer overflow: " + num);
        }
        work /= 10;
    }
    return (int) reversed;
}

Notice the check for integer overflow in the middle. It's a mistake of the caller to try to reverse an int that would turn out to be too big.

As with any non-trivial implementation, it's important to have unit tests:

@Test
public void testReverse_3() {
    assertEquals(3, reverse(3));
}

@Test
public void testReverse_34() {
    assertEquals(43, reverse(34));
}

@Test
public void testReverse_41() {
    assertEquals(14, reverse(41));
}

@Test
public void testReverse_123() {
    assertEquals(321, reverse(123));
}

@Test
public void testReverse_100() {
    assertEquals(1, reverse(100));
}

@Test
public void testReverse_123456789() {
    assertEquals(987654321, reverse(123456789));
}

@Test(expected = IllegalArgumentException.class)
public void testReverse_1234567899() {
    reverse(1234567899);
}

getPalindrome

As others already pointed out, getPalindrome is not a great name for this method.

It's also not great that it takes a String and converts it to integer, because it's an additional responsibility, so it violates the Single Responsibility Principle.

This way of declaring variables looks odd:

    int reverseCount = 0,
        currentNum = Integer.parseInt(line)
    ;

I'd recommend to just stick to traditional style:

    int reverseCount = 0;
    int currentNum = Integer.parseInt(line);

As with anything non-trivial, it's extremely helpful to have unit tests. I also included test cases suggested by @thepace. I renamed the method to stepsToPalindromic and made it take an integer parameter instead of String.

@Test
public void testStepsToPalindromic_8() {
    assertEquals("0 8", stepsToPalindromic(8));
}

@Test
public void testStepsToPalindromic_125() {
    assertEquals("1 646", stepsToPalindromic(125));
}

@Test
public void testStepsToPalindromic_195() {
    assertEquals("4 9339", stepsToPalindromic(195));
}

@Test
public void testStepsToPalindromic_0() {
    assertEquals("0 0", stepsToPalindromic(0));
}

@Test(expected = IllegalArgumentException.class)
public void testStepsToPalindromic_max() {
    stepsToPalindromic(Integer.MAX_VALUE);
}

@Test
public void testStepsToPalindromic_minus1() {
    assertEquals("0 -1", stepsToPalindromic(-1));
}

@Test
public void testStepsToPalindromic_minus195() {
    assertEquals("4 -9339", stepsToPalindromic(-195));
}

@Test
public void testStepsToPalindromic_9998() {
    assertEquals("6 8836388", stepsToPalindromic(9998));
}
\$\endgroup\$
6
\$\begingroup\$
  • Indentation and formatting currentNum = Integer.parseInt(line) ;
  • Is there a chance of an MAX_INT overflow for reverse(). Seems unlikely for the given contraints though.
  • Since n is an integer, so negatives are allowed. In that case .reverse() will cause problem. Please check the constraints.
  • getPalindrome() should return a palindrome instead of an output you wish to have. Instead either have the function name changed. (Though not a big concern but ensure that when I see a function name, it shoul dbe intuitive so that I do not have to check the code for the actual output.)
  • Test cases:
    1. Include 0, 9998 (max non palindromic n).
    2. Negatives (if constraints dont mention so).
    3. Invalid input. (Not handled by your program and may not be required but would help for a production code and not a programming challenge).

Optimisation:

  • reverse() though takes negligible time (in nanoseconds) but can be improved to handle all above cases along with speed in calculation. Ideone link

    private static int reverseInt(int n) {
        int rev = 0;
        while(n>0){
            rev = (rev*10)+n%10;
            n=n/10;
       }
       return rev;
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.