Get the number of digits of a power of 2, with large exponents?

Question

I am doing the following exercise: The number of digits of a power of 2.. The statement is:

What is the number of digits of a power of 2?
2 ---> 1 digit 
2 * 2 = 4 ---> 1 digit 
2 * 2 * 2 = 8 ---> 1 digit
  2 * 2 * 2 * 2 = 16 ---> 2 digits
  ... ... ... 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 1024 ---> 4 digits
Then, given the exponent, what would be the number of digits of that power?

I have tried the following answer:

import java.math.BigInteger; 
public class Power {
    public static long digit(long exp) {
    System.out.println("exp: "+exp);
    BigInteger pow = BigInteger.valueOf(2).pow((int)exp);
    return String.valueOf(pow).split("").length;
    }
}

However it times out with big exponents like: 562078812

How could we improve this solution? Is there any fastest answer?

I have also read:

take a look at https://www.geeksforgeeks.org/number-of-digits-in-2-raised-to-power-n/ — JavaMan, Feb 02 '20 at 12:18

score 3 · Accepted Answer · answered Feb 02 '20 at 12:16

3

The fastest answer is to use math. The number of digits in 2^n is (nlog₁₀2)+1 . You can achieve that by simply returning n * Math.log10(2) + 1. Good luck.

answered Feb 02 '20 at 12:16

Amir

134
1
1
11

score 1 · Answer 2 · answered Feb 02 '20 at 12:58

In decimal system, there will be exactly (n+1) digits in 10 power n.

10 power 1 has 2 digits.
10 power 2 has 3 digits.
10 power 3 has 4 digits.
...
.....
10 power n has (n+1) digits.

The trick here is to find number of decimal digits in the exponent of '2'.

The difficult way to find the answer is to actually calculate 2 power n and then count the number of digits. However, this method requires huge computing power.

The simpler answer lies in the difference between 10 and 2.

If power of 2 raises by 1 in binary system, then digits in decimal system raise only by log 2 base 10!

For a raise of n powers in binary, the equivalent will be (n *log2_base_10 + 1) in decimal system.

Working solution:

public class Power {
    public static long digit(long exp) {
        return (long) (Math.ceil(exp * Math.log10(2)) + 1);
    }

    public static void main(String[] args) {
        long exp = 50000000;
        System.out.println("Number of digits in 2 power " + exp 
                            + " = " + Power.digit(50000000));
    }
}

Output:

$ javac Power.java
$ java Power

Number of digits in 2 power 50000000 = 15051501

score 0 · Answer 3 · answered Feb 02 '20 at 12:37

0

Use static method like below to compute number of digits. I think this is faster way

static int countDigits(int n) 
{ 
    return (int)(n * Math.log10(2) + 1); 
}

answered Feb 02 '20 at 12:37

Omid

314
1
13

Get the number of digits of a power of 2, with large exponents?

3 Answers3