2
\$\begingroup\$

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

    BigInteger big = new BigInteger("2");
    big = big.pow(1000);
    String num = big.toString();
    System.out.println(num);
    int result = 0;
    for(char i : num.toCharArray()) {
        result += Integer.parseInt(String.valueOf(i));
    }
    System.out.println(result);
\$\endgroup\$
  • \$\begingroup\$ What kind of feedback are you looking for? Is there anything about the code you've posted that you're not satisfied with? \$\endgroup\$ – ShapeOfMatter Sep 11 at 14:22
  • \$\begingroup\$ yes, I feel that there is a better way. instead of converting BigInteger to string and then to charArray and again I return it to int \$\endgroup\$ – Omar Ahmed Sep 12 at 6:48
  • 1
    \$\begingroup\$ Use Character.getNumericalValue(char) instead of Integer.parseInt(String.valueOf(i)). \$\endgroup\$ – TorbenPutkonen Sep 13 at 10:38
  • \$\begingroup\$ @TorbenPutkonen yeah it's more clear. thanks a lot. \$\endgroup\$ – Omar Ahmed Sep 15 at 9:56
4
\$\begingroup\$

This looks good. I assume this results in correct answer.

  • What you can use instead of converting to String and back to int is to use divideAndRemainder method with 10 since we need to treat this as a base 10 number.
  • This method is available in BigInteger for situations like this.
  • We can also directly use BigInteger constants such as TWO and TEN.

Alternative Implementation

BigInteger big = BigInteger.TWO.pow(1000);
String num = big.toString();
System.out.println(num);

int result = 0;
BigInteger[] components;

components = big.divideAndRemainder(BigInteger.TEN);
while (components[0].signum() != 0) {
    result += components[1].intValue();
    components = components[0].divideAndRemainder(BigInteger.TEN);
}
result += components[1].intValue();
System.out.println(result);
  • I've used signum method here to check if result after integer division is zero.
  • Note: This seems to be creating lot of objects.

Benchmark with JMH

After the some discussion in comments with @TorbenPutkonen, I agreed with TorbenPutkonen that alternative implementation might be creating more objects. However there is no way to see which implementation performs faster without doing a benchmark.

public class X {

    public static void main(String[] a) throws Exception {
        org.openjdk.jmh.Main.main(a);
    }

    @State(Scope.Benchmark)
    public static class BenchmarkState {
        BigInteger multiple =  BigInteger.TWO.pow(1000);
        public BenchmarkState() {
            System.out.println(multiple);
        }
    }

    @Benchmark
    @Warmup(iterations = 5)
    public int withDivide(BenchmarkState x) {
        BigInteger[] components;
        components = x.multiple.divideAndRemainder(BigInteger.TEN);
        int result = 0;
        while (components[0].signum() != 0) {
            result += components[1].intValue();
            components = components[0].divideAndRemainder(BigInteger.TEN);
        }
        result += components[1].intValue();
        return result;
    }

    @Benchmark
    @Warmup(iterations = 5)
    public int withChars(BenchmarkState x) {
        String num = x.multiple.toString();
        int result = 0;
        for(char i : num.toCharArray()) {
            result += Integer.parseInt(String.valueOf(i));
        }
        return result;
    }

    @Benchmark
    @Warmup(iterations = 5)
    public int withCharsNumerical(BenchmarkState x) {
        String num = x.multiple.toString();
        int result = 0;
        for(char i : num.toCharArray()) {
            result += Character.getNumericValue(i);
        }
        return result;
    }

    @Benchmark
    @Warmup(iterations = 5)
    public int withCharAt(BenchmarkState x) {
        String num = x.multiple.toString();
        int len = num.length();
        int result = 0;
        for(int i = 0; i < len; i++) {
            result += Integer.parseInt(String.valueOf(num.charAt(i)));
        }
        return result;
    }

    @Benchmark
    @Warmup(iterations = 5)
    public int withCharsNumericalCharAt(BenchmarkState x) {
        String num = x.multiple.toString();
        int len = num.length();
        int result = 0;
        for(int i = 0; i < len; i++) {
            result += Character.getNumericValue(num.charAt(i));
        }
        return result;
    }
}
# Run complete. Total time: 00:21:29

Benchmark                    Mode  Cnt       Score      Error  Units
X.withCharAt                thrpt  200  117285.320 ±  644.505  ops/s
X.withChars                 thrpt  200  116882.706 ±  779.233  ops/s
X.withCharsNumerical        thrpt  200  110849.659 ± 3901.095  ops/s
X.withCharsNumericalCharAt  thrpt  200  121480.705 ± 2040.597  ops/s
X.withDivide                thrpt  200   11306.787 ±   35.711  ops/s
  • This concludes that original version is roughly 10x faster than divideAndRemainder
  • Original version is also slightly faster than using getNumericValue by itself.
  • However we can use charAt and avoid creating a character array too.

Why is using divideAndRemainder slow?

  • toString method of BigInteger uses a faster algorithm to create the string representation.
  • divideAndRemainder creates lot of BigInteger objects.
\$\endgroup\$
  • \$\begingroup\$ That 's what i looking for... thanks alot \$\endgroup\$ – Omar Ahmed Sep 12 at 10:59
  • 1
    \$\begingroup\$ @OmarAhmed Updated my answer with code. Also if you want to it would be more fun to write the BigInt yourself ;) \$\endgroup\$ – bhathiya-perera Sep 12 at 12:22
  • \$\begingroup\$ Looking quickly at the code in divideAndRemainder I'd say this approach results in about 2000 or more unnecessary object creations. Despite toString().toCharArray() creating an unnecessary array I would bet that it'd be much more efficient to do it char by char. \$\endgroup\$ – TorbenPutkonen Sep 13 at 9:16
  • \$\begingroup\$ @TorbenPutkonen doesn't Integer.parseInt(String.valueOf(i)) create temporary objects too? This avoids string conversion all together (except for printing). However I'm now curious to run a benchmark and see. 🤔 \$\endgroup\$ – bhathiya-perera Sep 13 at 10:13
  • 2
    \$\begingroup\$ @TorbenPutkonen I've updated the answer with a benchmark. Seems like you are correct. Good catch. :) \$\endgroup\$ – bhathiya-perera Sep 14 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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