Did I just increase the complexity of reversing a number?

Question

public class HelloWorld{

 public static void main(String []args){

    int  orig=103, reverse=0, mod;
    int numOfDigits=0;
    int n = orig;

    while (n>0){
        n /= 10;
        numOfDigits++;
    }
    n = orig;
    while (n > 0){
        mod = n % 10;
        reverse = reverse + (int)(mod * java.lang.Math.pow(10, numOfDigits-1));
        numOfDigits--;
        n /= 10;
    }

System.out.println("Reversed is : " + reverse);
 }

}

I do know that reverse = reverse + (int)(mod * java.lang.Math.pow(10, numOfDigits-1)); can be replaced by reverse = mod + (reverse*10).

Was wondering if I had just increased the complexity of a simple program by calculating total number of digits and applying power?

P.S: Kindly assume that orig can be taken as an input from the user and could be a number of any number of digits. I have hard coded only for experiment.

Stephen C · Accepted Answer · 2018-10-05T07:29:13.037

You didn't increase the complexity ... but you did make it slower. The expression pow(10, numOfDigits - 1) will be substantially slower than reverse = mod + (reverse * 10)

^{It is also possible that a computation that uses Math.pow instead of integer multiplication is inaccurate due to floating point imprecision. A double has only 52 bits of precision, compared with 63 for a long. In this example, this probably doesn't apply, but it is something to be wary of, in general}

score 1 · Answer 2 · answered Aug 11 '18 at 05:08

Probably, this would be the best approach with less iteration & complexity:

public class NumReverse {

public long reverseNumber(long number){

    long reverse = 0;
    while(number != 0){
        reverse = (reverse*10)+(number%10);
        number = number/10;
    } 
    return reverse;
}

public static void main(String a[]){
    System.out.println("Reversed is: "+new NumReverse().reverseNumber(103));
}
}

rsy56640 · Answer 3 · 2018-08-11T02:45:01.887

0

compute the multiply times and add times:
suppose f(x) = an * x^n + an-1 * x^n-1 + ... + a1 * x + a0
1. If calculate f(x) by computing one item by one item,
it will take (n+1) + n + (n-1) + ... + 1 + 0 = (n+1)(n+2)/2 multiply times and n addition times.
2. If calculate f(x) by n = n*10 + mod,
it will take n multiply times and n addition times.

Of course, if pow() has some optimization such as "divide and conquer", the complexity of pow() should be O(logN).

edited Aug 11 '18 at 02:45

answered Aug 11 '18 at 02:39

rsy56640

299
1
3
13

This is speculation. In fact, the real implementation doesn't work this way at all; see https://stackoverflow.com/questions/32418731/java-math-powa-b-time-complexity. But don't take my word for it: look at the source code! – Stephen C Aug 11 '18 at 03:49

Did I just increase the complexity of reversing a number?

3 Answers3