Checking whether a number is a power of 10

Question

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));
    }
}

Answer 1

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.

Answer 2

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;
}   

Answer 3

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

Answer 4

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));
}

Answer 5

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

Answer 6

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

Answer 7

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;
}

Answer 8

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)));
}

Answer 9

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')

Answer 10

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 /= 10;
    }

    return input == 1;
}

Answer 11

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);
}

Answer 12

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.