How to approach algorithms? Which is the preferred way?

Question

So I am learning Java and doing a bit of basic algorithms (still really new to this).

Say the requirement is to reverse an integer of 5143 so it becomes 3415.

Which of the following is the better way to do it (or is there an even better way)? The two different functions are reverse() and reverseNum (Ability to reverse 0 value is neglected):

public class ReverseIntegers {

public static void main(String[] args) {

reverseNum(5143);
reverse(5143);

}

public static void reverse(int number) {

    String numString = Integer.toString(number);
    String result = "";

    char[] cArray = numString.toCharArray();

    for (int i = (cArray.length - 1); i >= 0; i--) {
        result += Character.toString(cArray[i]);    // concatenate the String numbers in reverse order

    }

    System.out.println(Integer.parseInt(result));

}

public static void reverseNum(int number) {

    int numLength = Integer.toString(number).length();

    int[] numArray;
    numArray = new int[numLength];

    int numMod;
    int numModLength;
    int result = 0;


    for (int i = numLength - 1; i >= 0; i--) {

        numMod = (int)(number % Math.pow(10, i + 1));    // eliminate first integer value one by one
        numModLength = Integer.toString(numMod).length();

        while (numModLength > 1) {    // obtain the first integer value of the remainder
            numMod = (numMod / 10); 
            numModLength--;
        }

        numArray[i] = numMod;    // assign the first integer value to the array
    }

    int digits = numArray.length - 1;

    for (int i = 0; i < numArray.length; i++) {    // put numbers in the array in reverse sequence

        result += numArray[i] * Math.pow(10, digits);
        digits--;

    }

    System.out.println(result);

}
}

Answer 1

The first function is roughly equivalent to:

String rev = new StringBuilder().append(number).reverse().toString();
System.out.println(Integer.parseInt(rev));

The second function is (in my opinion) quite hard to read. It is also quite inefficient due to the repeated calls to Integer.toString().

A third alternative (which you haven't coded up) is to have a function that's purely based on integer maths and doesn't use strings at all. It'll probably be the most efficient of the lot. It will, however, require some care in how it deals with numbers that end in zeroes.

In my view the contest is between the first and the third alternatives; the second function has the shortcomings of both and the advantages of neither.

In the absence of any further information, I'd probably use the code at the start of this answer, and would replace it with something that doesn't using strings if and only if profiling the app suggests it's worth doing.

Answer 2

When analyzing algorithms consider the following (and others depending on your situation): development effort, resource cost, and maintainability.

• Development Effort - Which was more difficult / time consuming to create? You will have to answer that question. Could this be solved by a more elegant (StringBuffer.reverse()) solution?

• Resource Cost - It seems to be that the first is cheaper in most cases (first glance, I may be wrong), but this heavily depends on your problem (often they have the same complexity, here the first can be reduced to O(N) if you use a StringBuffer, but currently the second algorithm wins here).

For example, the choice may change depending on how many digits there are, which can cause memory or time problems at very large N (digits). Resource cost is often not important with small problems (will you be running this all the time)? If you invest too much into resource cost, you have increased development effort. This is why it is often suggested that optimization is done when a resource problem arises.

If you really need to know and you cannot determine by analysis of algorithms, an instinct should always be to empirically test the code.

• Maintainability - Will someone else looking at your code be able to quickly understand and change it? For me the simplicity of the first algorithm wins (by far).

Answer 3

The best way to approach an algorithm is to realize that the algorithm measures something that is distinct from the correctness of the program.

Assuming that two programs both provide the same output, can you prove that one performs better under certain circumstances? If you can, then you have made an argument that it is the better algorithm under those circumstances. As long as those circumstances hold, that implementation of the solution will be the better program.

A good example is an address book. Very simple address books are just notebooks. Addresses are written in as they are received. A more complex address book is printed with pages which provide easy indexing by the alphabet.

If you only write down addresses, and rarely look them up, the unsorted address book might be faster to use than the one where you must jump to the correct letter. If you mostly look up addresses that are rarely written down, then the name indexed address book is clearly superior. If you are trying to look up a name based on when it is written in the book, then the unsorted address book is better than the indexed one (although a date oriented address book might be even better).

So know you understand what the field of algorithms is meant to analyze, the only trick is that you have to get good at describing operations mathematically, and proving your point with more than mere anecdote.

Answer 4

You can achieve the same result using string operations:

int n = 5143;
String nStr = Integer.toString(n);
String nStrRev = new StringBuilder(nStr).reverse().toString();
int nRev = Integer.parseInt(nStrRev); // nRev == 3415

Answer 5

How about this:

public static int reverseInt(int n)
{
    int result = 0;
    while(n != 0)
    {
        result *= 10;
        result += (n % 10);
        n /= 10;
    }

    return result;
}

Answer 6

I would suggest to always check existing API because there is usually some handy method around already. Like:

StringBuffer.reverse()

Answer 7

Even better way:

new StringBuilder("" + number).reverse().toString()