Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a better way to check whether a number is a power of 10? This is what I've implemented:

    public class PowersOfTen {

    public static boolean isPowerOfTen(long input) {

        if (input % 10 != 0 || input == 0) {
            return false;
        }

        if (input == 10) {
            return true;
        }

        return isPowerOfTen(input/10);
    }

    public static void main(String[] args) {

        System.out.println("1000: " + isPowerOfTen(1000));
        System.out.println("4: " + isPowerOfTen(4));
        System.out.println("0: " + isPowerOfTen(0));
        System.out.println("10: " + isPowerOfTen(10));
        System.out.println("100: " + isPowerOfTen(100));
    }
}
share|improve this question
6  
@TomFenech If the input is an integer, it can't be a negative power of 10. Unless you mean something like -1000, which isn't power of 10. – Erick Wong Jan 19 at 19:05
2  
@ErickWong that's one of the reasons I asked; I was referring to numbers like 0.1, which would obviously require a different implementation. – Tom Fenech Jan 19 at 19:13
1  
@TomFenech that opens a massive can of worms. Remember floating point types can't exactly represent negative powers of 10 either. – Peter Green Jan 20 at 17:42
1  
1 is a power of 10 though, since 10 to the power of 0 is 1. This function returns false for 1. – Daniel Martin Jan 20 at 21:13
5  
Moderator's note to reviewers: Yes, there are many different ways to solve this problem. However, this being Code Review, answers must have some bearing on the code in the question. If you present an independent solution, you also need to include some justification. – 200_success Jan 20 at 22:55

13 Answers 13

up vote 35 down vote accepted

Recursing seems pretty heavy for this. You can use much the same logic but with a simple loop:

while (input > 9 && input % 10 == 0) 
  input /= 10;
return input == 1;

This checks to make sure the input is positive (since negative numbers and zero can't be powers of 10) and a multiple of 10 (as all powers of 10 greater than 1 obviously are). It does the positive check first as a small micro-optimization; the short-circuit evaluation will avoid performing an unnecessary division to compute an unneeded modulus.

If both conditions are met it does an integer division by 10 and repeats the process. For any power of 10, this will terminate with the value 1; if 1 itself is passed in, it will do so without ever executing the body of the while loop.

share|improve this answer
1  
Making it while (input > 9 ... instead avoids some superfluous extra calculations for inputs of 1 through 9 (and 10^x multiples of those as well). – Jeff Y Jan 20 at 17:33
    
@JeffY How will it handle negative powers of 10? For inputs like 0.1 or 0.01 etc. – Paras D Pain Jan 20 at 18:31
    
See: long input. – Jeff Y Jan 20 at 19:42
1  
@ParasDPain the input is a long, which is an integral type. Fractional values are not possible. – Mark Reed Jan 20 at 19:44
    
I see, the requirements. – Paras D Pain Jan 20 at 19:47

You could also just list them out as there aren't that many in range of the long datatype.

Advantages over the code in the OP is that it is simple, clear, and correct.

Disadvantages are that some might consider it verbose. Additionally a (potential) micro optimisation might be to break the comparisons up into smaller groups and perform a binary search to reduce the number of comparisons in the case that a non power of 10 is passed.

public static boolean isPowerOfTen(long input) {
  return 
    input == 1L
  || input == 10L
  || input == 100L
  || input == 1000L
  || input == 10000L
  || input == 100000L
  || input == 1000000L
  || input == 10000000L
  || input == 100000000L
  || input == 1000000000L
  || input == 10000000000L
  || input == 100000000000L
  || input == 1000000000000L
  || input == 10000000000000L
  || input == 100000000000000L
  || input == 1000000000000000L
  || input == 10000000000000000L
  || input == 100000000000000000L
  || input == 1000000000000000000L;
}   
share|improve this answer
1  
Indeed, or put them in a static (or otherwise, if conciseness is desirable) set which you can test membership of. – Erick Wong Jan 19 at 19:27
32  
Sorting Hat version. – Insane Jan 20 at 10:33
2  
Also a bit slow because all ors will be making the CPU have to branch many times but.. wait this is Java anyway so it's gonna be slow no matter what. – mathreadler Jan 21 at 4:36
1  
@FilipHaglund - Yes. It would need to be tested whether it helps or hinders - and even if it did help unless this is a critical path in the code the loss of clarity probably wouldn't compensate anyway. – Martin Smith Jan 21 at 9:38
4  
This answer is the base for this code-golf question – removed Feb 3 at 12:44

I consider your code to be incorrect, because I expect isPowerOfTen(1) to be true.

share|improve this answer
1  
You're right, good pick up. – jcm Jan 19 at 6:14
7  
Just change if (input == 10) for if (input == 1) and put that if block first. – abligh Jan 19 at 8:25
    
So "Is there a better way to check whether a number is a power of 10? " – Martin Smith Jan 20 at 22:58
9  
@MartinSmith this is more of a valid review point than simply rewriting the solution and saying "here you go" – Quill Jan 20 at 23:04

Mathematical alternative

There's Math.log10():

public static boolean isPowerOfTen(long value) {
    // updated answer - check for precision in if statement
    if (value >= 1e14) {
        try {
            return isPowerOfTen(BigDecimal.valueOf(value)
                                    .divide(BigDecimal.valueOf(1e14)).longValueExact());
        } catch (ArithmeticException e) {
            return false;
        }
    }
    double power = Math.log10(value);
    return Double.isFinite(power) && Math.round(power) == power;
}

Take care about precision, as mentioned in @ErickWong's comment. I've updated my answer above to handle values above 1e14, which seems to be the point where precision is lost.

Unit testing

Your simple tests in main() should be converted into the form of a unit test. For example, using TestNG:

public void testPowerOfTen() {
    assertTrue(isPowerOfTen(1)); // 10^0, as mentioned by @200_success
    assertTrue(isPowerOfTen(1000));
    assertFalse(isPowerOfTen(4));
    assertFalse(isPowerOfTen(0));
    assertTrue(isPowerOfTen(10));
    assertTrue(isPowerOfTen(100));
}
share|improve this answer
4  
Have you tested this against precision issues? The log10 of 10^18+1 is going to be very close to 18, likely closer than can be represented faithfully in double precision. – Erick Wong Jan 19 at 6:51
    
@ErickWong entirely valid point. :) Have updated my answer. – h.j.k. Jan 19 at 7:26
3  
I don't like this solution since 1) Assuring myself that it's correct is too hard. Floating point rounding is tricky. 2) The use of an exception as part of the core logic. – CodesInChaos Jan 19 at 14:52
    
@CodesInChaos personally, I think the main problem with my approach starts with the if (value >= 14). If that can be handwaved away, I reckon the original approach is OK-ish. Hence the 'take care about precision' emphasis... ;) – h.j.k. Jan 19 at 15:40
3  
@h.j.k. The part you would like to handwave away is essential to the correctness of the method. Fundamentally the problem is shoehorning a function like log10 whose correctness is only approximate into a problem that requires exactness. – Erick Wong Jan 19 at 19:14

In the same vein as Martin Smith's answer, you could store all powers of 10 in order in an array and then do a binary search:

private static final long[] powersOf10 = new long[] {
    1L, 10L, 100L, 1000L, 10000L, 100000L, 1000000L, 10000000L,
    100000000L, 1000000000L, 10000000000L, 100000000000L,
    1000000000000L, 10000000000000L, 100000000000000L, 1000000000000000L,
    10000000000000000L, 100000000000000000L, 1000000000000000000L
};

static boolean isPowerOfTen(long input) {
    return Arrays.binarySearch(powersOf10, input) >= 0;
}

Note: this method is far less efficient than Martin's (about 2.5x as slow on my computer) for this small data set but it scales much better to large data sets.

On the other hand, if you need extreme speed then this algorithm, based on 5gon12eder's comment, might be worth using. It switches on the lower bits of the input (you can't switch on a long) and if it gets a hit, it performs a linear search.

static boolean isPowerOfTen(long input) {
    switch ((int)input) {
        case (int)1L:
        case (int)10L:
        case (int)100L:
        case (int)1000L:
        case (int)10000L:
        case (int)100000L:
        case (int)1000000L:
        case (int)10000000L:
        case (int)100000000L:
        case (int)1000000000L:
        case (int)10000000000L:
        case (int)100000000000L:
        case (int)1000000000000L:
        case (int)10000000000000L:
        case (int)100000000000000L:
        case (int)1000000000000000L:
        case (int)10000000000000000L:
        case (int)100000000000000000L:
        case (int)1000000000000000000L:
            return linearSearch(input);
        default:
            return false;
    }
}

// from Martin Smith's answer:
private static boolean linearSearch(long input) {
    return
        input == 1L
            || input == 10L
            || input == 100L
            || input == 1000L
            || input == 10000L
            || input == 100000L
            || input == 1000000L
            || input == 10000000L
            || input == 100000000L
            || input == 1000000000L
            || input == 10000000000L
            || input == 100000000000L
            || input == 1000000000000L
            || input == 10000000000000L
            || input == 100000000000000L
            || input == 1000000000000000L
            || input == 10000000000000000L
            || input == 100000000000000000L
            || input == 1000000000000000000L;
}

Benchmark computing on first billion positive ints:

  • linear search (Martin Smith): 2970 ms
  • binary search: 6908 ms
  • switch on hash then linear search: 1519 ms
share|improve this answer
    
I think a switch statement would be the fastest (and most readable?) solution here. – 5gon12eder Jan 20 at 19:50
1  
@5gon12eder Java doesn't support switching on longs. – Solomonoff's Secret Jan 20 at 19:54
    
Ups, I forgot that… You could “hash” the bits of a long into an int and switch over that but It would be less obvious. – 5gon12eder Jan 20 at 20:00
    
@5gon12eder If you hash, you would get false positives. You could hash and then if you get a match, run an exact algorithm. That would be much faster and I will update this answer accordingly. – Solomonoff's Secret Jan 20 at 21:00
    
Well, the idea actually was to resolve hash collisions with ifs in the respective cases. But your version looks good too and is harder to get wrong. – 5gon12eder Jan 20 at 22:48

Iterative version

This suggestion is similar to @200_success's answer. This can be contracted into a for-loop if you are into that sort of thing :). Points of interest:

  • No recursion. Recursion makes for elegant code but those extra function calls compared to an iterative function sometimes comes at a significant performance penalty.
  • Using multiplication instead of division (which is supposed to be faster but I'm no authority on that)
  • No special handling of 0, 1 or negative input numbers. Base needs checking though.
  • Other bases than 10 can be used.

Java:

public static boolean isPowerOf(long input, long base) {
    if (base < 2) throw new IllegalArgumentException("base must be 2 or larger");
    //find the biggest number that is safe to multiply base with without getting integer oveflow
    long safeMultiplier = Long.MAX_VALUE / base;
    long x = 1;
    while (x < input && x <= safeMultiplier) {
        x *= base;
    }
    return x == input;
}

BigInteger version

Because sometimes Long is just not long enough :)

public static boolean isPowerOf(BigInteger input, BigInteger base) {
    if (base.compareTo(BigInteger.ONE) != 1) {
        throw new IllegalArgumentException("base must be 2 or larger");
    }
    BigInteger x = BigInteger.ONE;
    int comparison;
    while ((comparison = x.compareTo(input)) == -1) {
        x = x.multiply(base);
    }
    return comparison == 0;
}

Recursive version

Recursive version still using multiplication instead of division. Putting the recursive call last in the function (like you also did) is a nod towards languages that can perform tail call optimization (http://c2.com/cgi/wiki?TailCallOptimization & https://en.wikipedia.org/wiki/Tail_call). I don't think Java does that however.

public static boolean recursiveIsPowerOf(long input, long base) {
    if (base < 2) throw new IllegalArgumentException("base must be 2 or larger");
    //find the biggest number that is safe to multiply base with without getting integer oveflow
    long safeMultiplier = Long.MAX_VALUE / base;
    if (safeMultiplier < base)
        return input == base;

    return recursiveIsPowerOf(input, base, 1);
}

private static boolean recursiveIsPowerOf(long input, long base, long x) {
    return (x >= input || x < 0) ? x == input : recursiveIsPowerOf(input, base, x * base);
}

Edit(s):

  • Added integer overflow check as per @ErickWong's suggestion
  • Added check for valid base (> 1)
  • Added BigInteger version
  • Fixed faulty overflow checks
share|improve this answer
1  
I think the iterative version will go into an infinite loop if the input is too large relative to MAX_INT/base. Have you tested this on an input that is approximately 2/3 times MAX_INT? – Erick Wong Jan 19 at 19:22
1  
@ErickWong Wong You are right. As java seem to silently wrap around on integer overflow it will go into an infinite loop. Good catch. I added an overflow check. I love that my answer to a code review post just got reviewed. :) – Max Jan 20 at 8:51
1  
Thanks, unfortunately the overflow check isn't sufficient. It's fine when base == 2 but for larger bases it is entirely possible for 10*x to overflow to a positive value. A safer way to check for overflow is to spend a single divide outside the for loop to find the maximum value that it's ok to multiply base by. – Erick Wong Jan 20 at 18:30

No divisions, no moduli, no recursion? Here we go:

public static boolean power10(int n) {
    int max_power10 = 100000; //whatever you can accept given your type
    int i = 1;
    while ( i != n && i != max_power10) i *= 10;   
    return i == n;
}

Improvement:

public static boolean power10(int n) {
    int max_power10 = 100000; //whatever you can accept given your type
    if (n > max_power10 ) return false;
    int i = 1;
    while (i < n) i *= 10;   
    return i == n;
}
share|improve this answer
    
why not a simple while ( i < n)? – FranMowinckel Feb 3 at 22:06
    
@FranMowinckel because it may cause overflow. Think about the case in which n is the maximum int value. – DarioP Feb 4 at 7:45
1  
C'mon, that's just a limit case that you can check before (i.e. if (n > max_power10) return false) – FranMowinckel Feb 4 at 8:31

IMO it would be cleaner as:

public static boolean isPowerOfTen(long input) {
    if (input <= 0 ) {
        // powers of 10 can't be 0 or negative
        return false;
    }

    // don't have to worry about negative powers since long input
    // doesn't hold fractions
    for (int pow = 0; pow <= Math.log10(Long.MAX_VALUE); ++pow) {
        if (input == (long)Math.pow(10, pow)) {
            return true;
        }
    }
    return false;
}

Math.log10(Long.MAX_VALUE) will yield the maximum power of 10 that will fit into a long, the floor of which is (truncated by implicit conversion to) 18.

From here we can also easily make the method generic by replacing references to 10 and Math.log10. Java doesn't have a Math.logb method, but recall: logb(x) = logc(x) / logc(b). So logb(Long.MAX_VALUE) = Math.log(Long.MAX_VALUE) / Math.log(b):

public static boolean isPowerOf(long input, int base) {
    if (input <= 0 ) {
        return false;
    }

    for (int pow = 0; pow <= Math.log(Long.MAX_VALUE) / Math.log(base); ++pow) {
        if (input == Math.floor(Math.pow(base, pow))) {
            return true;
        }
    }
    return false;
}

But we can also eliminate the loop with a little math to find the power directly and check if it is an integer:

public static boolean isPowerOf(long input, int base) {
    if (input == 0) {
        return false;
    }

    // use Math.abs since if the argument is NaN or less than zero to Math.log, 
    // then the result is NaN. This makes it work for negative inputs and bases
    Double power = Math.log(Math.abs(input)) / Math.log(Math.abs(base));

    // power might have lost precision, so I'm trying floor and ceiling. These are integers so if either yields the input, return true
    return (input == (long)Math.pow(base, Math.floor(power)) ||
            input == (long)Math.pow(base,  Math.ceil(power)));
}
share|improve this answer
2  
1) I'd avoid using floating point for integer problem, that makes reasoning about it far too difficult. Even if it happens to be correct, it requires far too much thinking to make sure it's correct. 2) Your code is clearly wrong, since Math.pow returns a double which can't represent every valid long. – CodesInChaos Jan 19 at 14:25
    
3) You could use BigInteger.pow instead of math.pow. 4) rounding the power to an integer would be simpler than testing both floor and ceil. – CodesInChaos Jan 19 at 14:53

Iteration would be more efficient than recursion.

Also input == 1 should count as a power of 10.

public static boolean isPowerOfTen(long input) {
    while (input > 1) {
        if (input % 10 != 0)
            return false;
        input = input / 10;
    }

    if (input == 1) {
        return true;
    }

    return false;
}

Even shorter version (suggested by Landei – thanks!):

public static boolean isPowerOfTen(long input) {
    while (input > 1) {
        if (input % 10 != 0)
            return false;
        input = input / 10;
    }

    return input == 1;
}
share|improve this answer
4  
I'm always baffled when I see code like this. Why the last if? Why not simply return input == 1? – Landei Jan 19 at 15:07
    
@Landei Well, me too. But I've seen code like this so many times here, that I started to believe this is a preferred style in Java programmers community. Corrected now. – CiaPan Jan 19 at 21:18

This is for fun, but what about this very basic solution?:

String.valueOf(x).matches("^10*$")

It should also work for long and BigDecimal's using toPlainString().

BTW I know that it's not high performance :P.

Also as a curiosity, any power of 10 in binary representation ends with itself:

1 -> b'1'
10 -> b'x10'
100 -> b'x100'
1000 -> b'x1000'
...

(where x is a sequence of '1' and '0')

share|improve this answer
    
@WashingtonGuedes shame on me! thanks! what a silly mistake – FranMowinckel Feb 3 at 11:11
    
Anyways +1.. I'd do this too without thinking two times... I personally like to extrapolate the regex's purpose – removed Feb 3 at 11:14

Here is one if we would want to avoid CPU-branching, which would be nice in compiled languages like C or C++ for CPUs which have broad instruction pipelines. It counts all non-zeros and ones in base 10.

The idea is: if and only if there are no larger-than-ones and exactly one 1, then we have a power of 10.

int ispow10(int aInput){
  int lCntO = 0, lCnt1 = 0, lTmp = 0, i = 0;
  for( i=0 ;i < 10; i++, aInput /= 10 ){
    lTmp = aInput % 10;
    lCntO += (lTmp > 1);
    lCnt1 += (lTmp == 1);
  }
return (lCntO == 0)&(lCnt1==1);
}
share|improve this answer

I know it's possibly not the best option, but I always find interesting to approach math-y simple problems from a human perspective and no one suggested the approach yet of, in this case, looking at how the number is written:

boolean isPowerOfTen(int n) {
    char[] digits = (n+"").toCharArray();
    if (digits[0] != '1') return false;
    for (int i = 1; i<digits.length; i++) {
      if (digits[i] != '0') return false;
    }
    return true;
}

You can easily extend it for negative powers (0.000001) and it's arguably much easier to read and short than other methods, though it has a worse performance.

share|improve this answer

I'm not going to comment on your method, but rather, your code:


Indentation:

Your indentation is off here:

public class PowersOfTen {

public static boolean isPowerOfTen(long input) {

The method declaration should be indented one level below the class declaration.


Spacing

You're missing spaces between your operators in the following block:

return isPowerOfTen(input/10);

Using appropriate helpers:

For code with code duplication like below, you should rewrite them to call a helper method, so that you can extract as much duplicate logic out as possible:

    System.out.println("1000: " + isPowerOfTen(1000));
    System.out.println("4: " + isPowerOfTen(4));
    System.out.println("0: " + isPowerOfTen(0));
    System.out.println("10: " + isPowerOfTen(10));
    System.out.println("100: " + isPowerOfTen(100));
share|improve this answer

protected by Jamal Jan 20 at 21:51

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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