2

I have a number (64-bit int) and want to know if it's a pure power of 10. That is to say, a 1 followed 0 or more by zeroes. Is there an efficient way of doing this that does not involve turning it into a String?

Currently I'm doing this:

Kotlin

fun isPowerOf10(n: Long): Boolean {
    val logN = Math.log10(myInt.toDouble())
    return logN != Math.floor(logN)
}

Java

static boolean isPowerOf10(long n) {
    double logN = Math.log10((double) myInt);
    return logN != Math.floor(logN);
}

But it fails with isPowerOf10(999_999_999_999_999_999) (and the negative version), due to precision loss when converting to a double and taking log10, which outputs precisely 18.0.

Ky -
  • 30,724
  • 51
  • 192
  • 308
  • 2
    Considering how few cases there are, a simple `switch` might be reasonable. – user2357112 Apr 08 '17 at 02:22
  • 2
    Or similarly simply make a loop to preopulate a `HashSet`. Whatever you do, don't use double/logarithm logic to do pure integer checks otherwise you'll be at the mercy of float accuracy as you saw with 999_999_... – Blake O'Hare Apr 08 '17 at 02:23
  • Have you tried using the BigDecimal type, i don't know if there is a math library of it but it works better with precision than the Double type. – jonhkr Apr 08 '17 at 02:23
  • @jonhkr I consider `BigDecimal` close enough to `String` in this instance to avoid it~ :P – Ky - Apr 08 '17 at 02:24
  • @jonhkr BigDecimal is a wildly inefficient way to do this – pvg Apr 08 '17 at 02:25
  • @SumitGulati 420%10 == 0, so no, in that case it is not a power of 10 (1, 10, 100, 1000, ...) – Rik Schaaf Apr 08 '17 at 02:32
  • 2
    http://codereview.stackexchange.com/questions/117203/checking-whether-a-number-is-a-power-of-10 – Sumit Gulati Apr 08 '17 at 02:33

7 Answers7

9

What you could do is a simple while loop:

static boolean isPowerOf10(long n) {
    while(n > 1 && n % 10 == 0){
        n /= 10;
    }
    return n == 1;
}

Or maybe even better, check for the powers of 10 themselves since there are only 19 in a long (ref):

public static boolean isPowerOf10(long n) {
  return 
    n == 1L
  || n == 10L
  || n == 100L
  || n == 1000L
  || n == 10000L
  || n == 100000L
  || n == 1000000L
  || n == 10000000L
  || n == 100000000L
  || n == 1000000000L
  || n == 10000000000L
  || n == 100000000000L
  || n == 1000000000000L
  || n == 10000000000000L
  || n == 100000000000000L
  || n == 1000000000000000L
  || n == 10000000000000000L
  || n == 100000000000000000L
  || n == 1000000000000000000L;
}
Community
  • 1
  • 1
Rik Schaaf
  • 1,101
  • 2
  • 11
  • 30
  • Can't you get away with `n > 10 && n % 10 == 0` .... it *would* be infinitesimally more efficient :) – juanpa.arrivillaga Apr 08 '17 at 02:41
  • @juanpa.arrivillaga No because then for n=10 you would not satisfy that n>10 and therefore the return statement would return false, because 10 == 1 is false. – Rik Schaaf Apr 08 '17 at 02:44
  • @juanpa.arrivillaga 10 raised to the power 0 is 1. `while(n > 10 && n % 10 == 0){ n /= 10; } return n == 10;` would not work in that case –  Apr 08 '17 at 02:46
  • @juanpa.arrivillaga I think you can make it n > 9 though – Rik Schaaf Apr 08 '17 at 02:49
  • @RikSchaaf d'oh! What was I thinking! It actually doesn't. If fails for numbers less than 10 but not equal to 1! – juanpa.arrivillaga Apr 08 '17 at 02:57
  • I'd guess that if you are really set on efficiency, the bunch-of-ors variant would be faster. Division is slow. – pvg Apr 08 '17 at 02:58
  • @pvg It is a common misconception that division is slow. While it does use more cycles to compute the divided number, it is on average dwarfed by tasks such as writing to memory. See http://stackoverflow.com/questions/226465/should-i-use-multiplication-or-division for more detail. – Rik Schaaf Apr 08 '17 at 03:17
  • @Supuhstar since long integers have a fixed max value, you can unroll the loop https://en.wikipedia.org/wiki/Loop_unrolling – Rik Schaaf Apr 08 '17 at 03:19
  • @RikSchaaf that's about division by two, which a compiler or JIT can special case. Here you have multiple divisions compared to a bunch of ors. A person less argumentative and lazy than me would probably JMH it. – pvg Apr 08 '17 at 03:26
  • @pvg I mainly tried to refer to 'How long the pipeline difference is is completely hardware dependant. Last hardware I used was something like 9 cycles for a FPU multiply and 50 cycles for a FPU divide.', a quote from the excepted answer that wasn't just about divide by 2, which is of course not cpu intensive considering PCs are base 2. – Rik Schaaf Apr 08 '17 at 04:16
  • @juanpa.arrivillaga that is true, because you don't check if the value is 1 at the end. – Rik Schaaf Apr 08 '17 at 04:24
  • @RikSchaaf can you demonstrate that in your example? – Ky - Apr 08 '17 at 04:40
  • @Supuhstar basically it would be manually writing out if a number is divisible by 10, 100, etc using modulo, but http://codereview.stackexchange.com/a/117294 shows an even more optimized solution as it doesn't require arithmetic, only logic. – Rik Schaaf Apr 08 '17 at 04:47
  • @RikSchaaf I don't think any of these very qualified and narrow statements add up to 'division is slow (compared to other arithmetical or logical operations) is a myth'. It's a mathematical reality. I did also try a quick naive benchmark of the or easily outperforms the mod-and-div version. This is notable as the exhaustive or has local worst-case performance for every single negative match - i.e. in uniformly distributed inputs, just about always. – pvg Apr 08 '17 at 07:38
  • @pvg the advantage is (if the compiler and jvm are smart enough) that the modulo and division are calculated at the same time by the cpu which means that the only statements per loop cycle would be >, ==, /% and assignment. I do however suspect that java doesn't optimize for this so in that case you are indeed correct. Also my previous comment directed at Supuhstar is probably the fastest implementation – Rik Schaaf Apr 08 '17 at 15:41
  • @RikSchaaf I think you underestimate how slow division is compared to logical ops. It's really that slow and measurement bears this out. – pvg Apr 08 '17 at 15:48
  • @pvg There is a difference between floating point division and integer division. I think it is true that floating point division is way slower. I don't have confirmation for that though. For integer division vs integer addition I performed a test: 200 million loop cycles with either a value divided by 10 or a value + 10. Results over an average of 100 trials: division 239.015ms, addition 213.366ms So the average delay that division has over addition is (239.015ms-213.366ms)/2e8=1.28e-7ms = 0.128 nanoseconds per operation. This method will use at most 38 division/modulo operations = 4.87ns loss – Rik Schaaf Apr 08 '17 at 16:53
  • @pvg I now performed the same test for floating point as well: there is about 8 ms difference between the 2, which equates to 0.04ns per operation. This surprises me (rerunning gives me the same results), but it seems that modern cpu implementations of fp division are almost on par with addition. – Rik Schaaf Apr 08 '17 at 17:06
  • @pvg the == operator is indeed faster, about a factor 10. – Rik Schaaf Apr 08 '17 at 17:10
  • The logic tower version ended up being the one I used. Ridiculously fast and not unreasonably long – Ky - Aug 14 '19 at 13:12
6

This is another way you can check if the number is a power of 10. This code leverages on the fact that there are only a few numbers that fit in the long data type and are a power of 10.

public static boolean isPowerOfTen(long number){
        long[] powersOfTen = new long[] {
            1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000
        };

        return Arrays.binarySearch(powersOfTen, number) >= 0;
}
  • 2
    You could make it even faster by using a `HashMap`!! (Assuming that you only have to set the map up once but could call the method many times.) – ajb Apr 08 '17 at 03:41
  • @ajb I was thinking about setting a hashmap once as you pointed out. I could only come up with putting the hasmap in the main() method and passing it to the function or creating a static hashmap in my class Although they work, putting something used only by this function in the main method or creating the hashmap as part of the class does not seem an elegant solution. Any advice on how can I do it better? –  Apr 08 '17 at 05:21
  • Create a new class that defines the `isPowerOfTen` method. The map can be a private class variable (`static`) in your class and can be initialized with a static initializer block if you need code to do it. – ajb Apr 08 '17 at 05:59
  • You can make the array `static` to make this much more efficient. – Peter Lawrey Apr 08 '17 at 06:37
  • @ajb Why would `HashMap` be faster than a binary search on a sorted array? IMO they perform about the same number of operations, and the array version has much better memory locality – voddan Apr 08 '17 at 09:04
  • @voddan HashMap's get is theoretically O(1) and worst case o(n) (in our case I expect O(1), since there is really few elements), while binary search is O(log(n)). – glee8e Apr 08 '17 at 10:41
  • I just realized I should have said "hash map" and not `HashMap`. Using Java's `HashMap` has a lot of unnecessary overhead, since it has to be general and will set up buckets. But it's very simple to set up an efficient hash map by finding a prime number _p_ such that all the values 10^k % _p_ will be different. Then the function then becomes: compute `number % p`; look up in the table and make sure the key in the table equals `number`; if so, return the logarithm from the table. – ajb Apr 08 '17 at 15:07
  • @voddan It's not a matter for opinion. See my above comment; a hash map lookup would be just a few operations, while a binary tree lookup would require a loop with 5 or 6 iterations every time you give it a number that's not in the table. – ajb Apr 08 '17 at 15:13
2

To make the second part of Rik Schaaf's answer in Kotlin, you could do something like:

val Long.isPowerOfTen get() = when (this) {
    1L,
    10L,
    100L,
    1000L,
    10000L,
    100000L,
    1000000L,
    10000000L,
    100000000L,
    1000000000L,
    10000000000L,
    100000000000L,
    1000000000000L,
    10000000000000L,
    100000000000000L,
    1000000000000000L,
    10000000000000000L,
    100000000000000000L,
    1000000000000000000L -> true
    else -> false
}
Ruckus T-Boom
  • 4,566
  • 1
  • 28
  • 42
1

We can take help of String class

return Math.pow(10,String.valueOf(x).length()-1) == x;
Bulat
  • 720
  • 7
  • 15
Shyam
  • 9
  • 2
1

Approach using String

boolean isPowerOfTen(int n){

  if( n == 1)
    return true;

  String num = String.valueOf(n);

  if(num.charAt(0) == '1' && Integer.parseInt(num.substring(1)) == 0)
      return true;
  else
     return false;
}

Here, we check whether the first char is '1' AND
whether the substring formed by discarding the first character is 0.

This won't work for 10^0, which is 1. Handled this case.

This is not as efficient as the Mathematical approach.

saintlyzero
  • 1,632
  • 2
  • 18
  • 26
1

Also works for negative powers.

boolean isPowerOf10(long number) {
    while (number % 10 == 0 && number != 0) {
        number = number / 10;
    }
    return Math.abs(number) == 1;
}
michalavis
  • 79
  • 1
  • 8
0

This solution also works for negative powers. e.g 10 ^ -3

public boolean isPowerOfTen(double n) {
   return (Math.pow(10,Math.log10(n)) == n);
}
Olufemi Thompson
  • 1
  • 1