35
\$\begingroup\$

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));
    }
}
\$\endgroup\$
  • 6
    \$\begingroup\$ @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. \$\endgroup\$ – Erick Wong Jan 19 '16 at 19:05
  • 2
    \$\begingroup\$ @ErickWong that's one of the reasons I asked; I was referring to numbers like 0.1, which would obviously require a different implementation. \$\endgroup\$ – Tom Fenech Jan 19 '16 at 19:13
  • 1
    \$\begingroup\$ @TomFenech that opens a massive can of worms. Remember floating point types can't exactly represent negative powers of 10 either. \$\endgroup\$ – Peter Green Jan 20 '16 at 17:42
  • 1
    \$\begingroup\$ 1 is a power of 10 though, since 10 to the power of 0 is 1. This function returns false for 1. \$\endgroup\$ – Daniel Martin Jan 20 '16 at 21:13
  • 7
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success Jan 20 '16 at 22:55

12 Answers 12

39
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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). \$\endgroup\$ – Jeff Y Jan 20 '16 at 17:33
  • \$\begingroup\$ @JeffY How will it handle negative powers of 10? For inputs like 0.1 or 0.01 etc. \$\endgroup\$ – Paras Jan 20 '16 at 18:31
  • \$\begingroup\$ See: long input. \$\endgroup\$ – Jeff Y Jan 20 '16 at 19:42
  • 1
    \$\begingroup\$ @ParasDPain the input is a long, which is an integral type. Fractional values are not possible. \$\endgroup\$ – Mark Reed Jan 20 '16 at 19:44
  • \$\begingroup\$ I see, the requirements. \$\endgroup\$ – Paras Jan 20 '16 at 19:47
36
\$\begingroup\$

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;
}   
\$\endgroup\$
  • 1
    \$\begingroup\$ Indeed, or put them in a static (or otherwise, if conciseness is desirable) set which you can test membership of. \$\endgroup\$ – Erick Wong Jan 19 '16 at 19:27
  • 40
    \$\begingroup\$ Sorting Hat version. \$\endgroup\$ – Insane Jan 20 '16 at 10:33
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – mathreadler Jan 21 '16 at 4:36
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Martin Smith Jan 21 '16 at 9:38
  • 5
    \$\begingroup\$ This answer is the base for this code-golf question \$\endgroup\$ – removed Feb 3 '16 at 12:44
30
\$\begingroup\$

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

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

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));
}
\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Erick Wong Jan 19 '16 at 6:51
  • \$\begingroup\$ @ErickWong entirely valid point. :) Have updated my answer. \$\endgroup\$ – h.j.k. Jan 19 '16 at 7:26
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – CodesInChaos Jan 19 '16 at 14:52
  • \$\begingroup\$ @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... ;) \$\endgroup\$ – h.j.k. Jan 19 '16 at 15:40
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – Erick Wong Jan 19 '16 at 19:14
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I think a switch statement would be the fastest (and most readable?) solution here. \$\endgroup\$ – 5gon12eder Jan 20 '16 at 19:50
  • 3
    \$\begingroup\$ @5gon12eder Java doesn't support switching on longs. \$\endgroup\$ – Solomonoff's Secret Jan 20 '16 at 19:54
  • \$\begingroup\$ 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. \$\endgroup\$ – 5gon12eder Jan 20 '16 at 20:00
  • \$\begingroup\$ @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. \$\endgroup\$ – Solomonoff's Secret Jan 20 '16 at 21:00
  • 1
    \$\begingroup\$ @Supuhstar That's almost certainly slower than binary search or switch until your table gets quite large. \$\endgroup\$ – Solomonoff's Secret Apr 9 '17 at 18:14
3
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Erick Wong Jan 19 '16 at 19:22
  • 1
    \$\begingroup\$ @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. :) \$\endgroup\$ – Max Jan 20 '16 at 8:51
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Erick Wong Jan 20 '16 at 18:30
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ why not a simple while ( i < n)? \$\endgroup\$ – FranMowinckel Feb 3 '16 at 22:06
  • \$\begingroup\$ @FranMowinckel because it may cause overflow. Think about the case in which n is the maximum int value. \$\endgroup\$ – DarioP Feb 4 '16 at 7:45
  • 2
    \$\begingroup\$ C'mon, that's just a limit case that you can check before (i.e. if (n > max_power10) return false) \$\endgroup\$ – FranMowinckel Feb 4 '16 at 8:31
1
\$\begingroup\$

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)));
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – CodesInChaos Jan 19 '16 at 14:25
  • \$\begingroup\$ 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. \$\endgroup\$ – CodesInChaos Jan 19 '16 at 14:53
1
\$\begingroup\$

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

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

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;
}
\$\endgroup\$
  • 4
    \$\begingroup\$ I'm always baffled when I see code like this. Why the last if? Why not simply return input == 1? \$\endgroup\$ – Landei Jan 19 '16 at 15:07
  • \$\begingroup\$ @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. \$\endgroup\$ – CiaPan Jan 19 '16 at 21:18
  • \$\begingroup\$ @Landei it's more explicit in its intent \$\endgroup\$ – Supuhstar Apr 9 '17 at 19:13
  • \$\begingroup\$ @Supuhstar Your brain needs to process four lines instead of one, there is branching and the method has two exit points instead of one. That might be "more explicit", but it is clearly less comprehensible. \$\endgroup\$ – Landei Apr 10 '17 at 7:56
  • \$\begingroup\$ @Landei four simpler lines that read more naturally in English than one terse line that reads more mathematically. Anyway, this is not the place for this. If you want to continue this discussion, feel free to email me at Supuhstar0@gmail.com \$\endgroup\$ – Supuhstar Apr 10 '17 at 10:17
0
\$\begingroup\$

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);
}
\$\endgroup\$
-1
\$\begingroup\$

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.

\$\endgroup\$

protected by Jamal Jan 20 '16 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.